Unit 13: Intractable Problems - Subjective Questions

Intractable problems are computational problems for which no polynomial-time algorithm is known, and whose exact solution generally requires excessive computational resources as the input size increases.

• A problem is generally considered tractable if it can be solved in polynomial time, such as for a constant .
• A problem is considered intractable if known algorithms require super-polynomial time, such as or .
• An undecidable problem has no algorithm that correctly terminates with an answer for every possible input.

Thus, an intractable problem is solvable in principle but may be impractical for large inputs, whereas an undecidable problem cannot be solved algorithmically for all inputs.

A polynomial-time algorithm has a running time bounded by for some constant , while an exponential-time algorithm may require time such as or .

Polynomial time is used as the conventional boundary of tractability because:

• Polynomial functions grow relatively slowly compared with exponential functions.
• Polynomial-time algorithms usually remain usable as the input size increases.
• Polynomial-time algorithms are closed under composition.
• Their classification is largely independent of reasonable computational models.

This boundary is theoretical rather than absolute. An algorithm with complexity is polynomial but impractical, while an exponential algorithm may still work for small inputs.

The three forms differ in the kind of output required:

• Decision problem: Determines whether a tour of cost at most exists. Its answer is either yes or no.
• Search problem: Finds a tour whose cost is at most , if such a tour exists.
• Optimization problem: Finds a tour having the minimum possible cost.

Complexity classes such as and are formally defined using decision problems. An optimization problem can often be related to its decision version by repeatedly asking decision questions with different bounds. If the optimization version can be solved efficiently, then the decision version can also be solved efficiently.

A non-deterministic algorithm is a theoretical algorithm that may choose among several possible next steps and is considered successful if at least one sequence of choices leads to an accepting result.

Its two conceptual phases are:

1. Guessing phase: Guess a candidate solution or certificate.
2. Verification phase: Check deterministically, in polynomial time, whether the candidate is valid.

Non-determinism is an abstract computational model and does not mean making random choices. A randomized algorithm follows choices according to a probability distribution and may have a probability of error or a variable running time. A non-deterministic algorithm accepts whenever an accepting computation path exists.

For a graph , the non-deterministic algorithm works as follows:

1. Guess an ordering of all vertices.
2. Verify that every vertex appears exactly once.
3. Check that for every .
4. Check that .
5. Accept if all checks succeed; otherwise reject that computation path.

The guessed ordering acts as a certificate. Its length is polynomial in the input size, and all verification steps can be completed in polynomial time. Therefore, the Hamiltonian Cycle decision problem belongs to . This does not establish that it can be solved deterministically in polynomial time.

Deterministic algorithms have exactly one defined next action for each state and input. Consequently, a given input produces one computation path.

Non-deterministic algorithms may conceptually select from multiple possible next actions. They accept an input if at least one computation path reaches an accepting state.

Key differences include:

• Choice: Deterministic computation has a unique choice; non-deterministic computation may have many choices.
• Computation paths: Deterministic computation follows one path; non-deterministic computation can be represented as a branching tree.
• Acceptance: A non-deterministic machine accepts if any branch accepts.
• Practical status: Determinism models conventional computers, whereas non-determinism is primarily a theoretical tool.

A deterministic machine can simulate all non-deterministic branches, but this simulation may require exponential time.

A certificate is additional information that demonstrates that a given instance is a yes-instance. A polynomial-time verifier is a deterministic algorithm that checks an instance and certificate in time polynomial in .

A decision problem belongs to if:

• Every yes-instance has a certificate whose length is polynomial in .
• The verifier accepts the pair in polynomial time.
• No certificate causes the verifier to accept a no-instance.

Formally, for a language ,

Thus, consists of decision problems whose yes-solutions can be verified efficiently.

is the class of decision problems solvable by a deterministic algorithm in polynomial time.

is the class of decision problems for which yes-instances have polynomial-length certificates verifiable in deterministic polynomial time. Equivalently, these problems can be solved by a non-deterministic machine in polynomial time.

The known relationship is:

This holds because a problem that can be solved quickly can also be verified quickly. It is unknown whether or .

If , every efficiently verifiable problem would also be efficiently solvable, profoundly affecting optimization, automated reasoning, scheduling, and cryptography. If , some problems would be efficiently verifiable but not efficiently solvable.

A polynomial-time many-one reduction from problem to problem , written , is a polynomial-time computable transformation such that:

The transformation converts every instance of into an equivalent instance of $B`.

Its significance is as follows:

• If and , then .
• If is computationally hard and , then is at least as hard as .
• Polynomial reductions are transitive: if and , then .

The reduction direction is crucial: to prove that is hard, one must reduce a known hard problem to , not reduce to the known hard problem.

The classes have the following meanings:

• : Decision problems solvable deterministically in polynomial time.
• : Decision problems whose yes-solutions are verifiable in polynomial time.
• -hard: Problems at least as hard as every problem in . Every problem in can be polynomially reduced to an -hard problem.
• -complete: Problems that are both in and -hard.

An -hard problem does not have to be a decision problem or even belong to $NP`; it may be an optimization problem or an undecidable problem. An $NP$-complete problem must be a decision problem with polynomially verifiable certificates. If any $NP$-complete problem has a polynomial-time algorithm, then $P=NP$.

An -completeness proof normally contains two major parts:

1. Prove that :

   • Specify a polynomial-length certificate.
   • Give a deterministic polynomial-time verification algorithm.

2. Prove that is -hard:

   • Select a known -complete problem .
   • Construct a polynomial-time reduction .
   • Prove both directions of correctness: an instance of is a yes-instance if and only if the constructed instance of is a yes-instance.
   • Show that the construction takes polynomial time and produces output of polynomial size.

A common error is reducing to . That only shows that is no harder than $Y`; it does not establish the hardness of $X$.

The Boolean Satisfiability Problem, or , asks whether there is an assignment of truth values to the variables of a Boolean formula that makes the formula true.

belongs to because:

• A truth assignment is a polynomial-length certificate.
• The formula can be evaluated under that assignment in polynomial time.

The Cook-Levin theorem states that is -complete. Its proof encodes the polynomial-time computation of a non-deterministic Turing machine as a Boolean formula that is satisfiable exactly when the machine has an accepting computation.

The theorem was historically important because it identified the first -complete problem. It provides a starting point for proving many other problems -complete through polynomial-time reductions.

In , the input is an arbitrary Boolean formula. In conjunctive normal form, the formula is an AND of clauses, where each clause is an OR of literals.

In -, every clause contains exactly three literals, or at most three literals under some definitions. For example:

Both problems ask whether a satisfying truth assignment exists, and both are -complete. - is especially useful because its uniform clause structure can be represented naturally by graph gadgets and combinatorial constraints. Reductions from - are commonly used to prove problems such as Clique, Vertex Cover, and Independent Set -complete.

First, Clique belongs to because a set of vertices can be checked in polynomial time to determine whether every pair is connected.

For the reduction, let a - formula contain clauses:

1. Create one vertex for each literal occurrence in each clause.
2. Connect vertices belonging to different clauses unless their literals contradict one another.
3. Ask whether the graph contains a clique of size .

Correctness:

• If the formula is satisfiable, select one true literal from each clause. The selected literals are pairwise consistent, so their vertices form a clique of size .
• If a clique of size exists, it must contain one vertex from each clause because vertices within the same clause are not connected. The selected literals are mutually consistent and can be extended to a truth assignment satisfying every clause.

The graph has polynomial size and is constructed in polynomial time. Therefore, Clique is -hard and, since Clique is also in , it is -complete.

The Vertex Cover decision problem asks whether a graph contains a set of at most vertices such that every edge has at least one endpoint in .

It belongs to because:

• The certificate is the proposed set .
• The verifier checks that .
• For every edge , it checks whether or .
• These operations require polynomial time.

A set is a vertex cover if and only if is an independent set. Therefore:

if and only if

This complement relationship gives polynomial-time reductions between the two decision problems.

A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex. The Hamiltonian Cycle decision problem asks whether such a cycle exists in a given graph and is -complete.

An Euler cycle is a closed walk that uses every edge exactly once. Its existence can be determined in polynomial time. For a connected undirected graph, an Euler cycle exists exactly when every vertex has even degree.

The main differences are:

• Hamiltonian Cycle focuses on visiting vertices exactly once.
• Euler Cycle focuses on using edges exactly once.
• Hamiltonian Cycle has no known polynomial-time characterization for general graphs.
• Euler Cycle can be recognized and constructed efficiently using degree conditions and graph traversal.

Their similar wording therefore does not imply similar computational difficulty.

The Subset Sum decision problem takes integers and a target and asks whether some subset has sum exactly .

A certificate can be represented by binary values , where means that is selected. The verifier checks whether:

The certificate and the arithmetic verification have polynomial length and running time, so Subset Sum belongs to .

A direct exhaustive-search algorithm considers all possible subsets. Since each of the elements may be either included or excluded, there are subsets. Its running time is therefore at least proportional to , apart from the work required to evaluate each subset. Subset Sum is also -complete.

Suppose an -complete problem has a deterministic polynomial-time algorithm. By definition, every problem has a polynomial-time reduction .

To solve :

1. Transform its input into an instance of in polynomial time.
2. Run the polynomial-time algorithm for .
3. Return the corresponding answer for .

The composition remains polynomial, so every problem in would belong to $P`. Since $P \subseteq NP$ is already known, this would prove:

Consequences would include polynomial-time methods for many scheduling, routing, logical reasoning, and combinatorial optimization problems. Many cryptographic systems based on assumed computational hardness could also become insecure, although practical effects would depend on the degree and constants of the discovered polynomial.

A pseudo-polynomial-time algorithm runs in time polynomial in the numeric values in the input, but not necessarily polynomial in the number of bits used to encode those values.

For example, the dynamic-programming algorithm for Subset Sum may run in time, where is the target. Since a binary representation of requires only bits, can be exponential in the encoded input length.

• A weakly -complete problem may admit a pseudo-polynomial algorithm and often becomes easier when numerical values are polynomially bounded. Subset Sum is a standard example.
• A strongly -complete problem remains -complete even when its numerical values are bounded by a polynomial in the input size. Such a problem is unlikely to have a pseudo-polynomial exact algorithm.

This distinction helps explain how the encoding of numerical data affects computational complexity.

Several strategies can be used to handle -hard problems in practice:

• Approximation algorithms: Produce solutions with provable bounds relative to the optimum.
• Heuristics and metaheuristics: Use methods such as greedy search, local search, simulated annealing, or genetic algorithms to obtain good solutions without guaranteed optimality.
• Parameterized algorithms: Confine exponential behavior to a parameter , giving running times such as .
• Branch and bound: Systematically search while pruning regions that cannot contain an improved solution.
• Dynamic programming: Exploit overlapping subproblems, special structure, or small numerical bounds.
• Special-case algorithms: Restrict the input to graph classes or instances that admit polynomial-time solutions.
• Preprocessing and kernelization: Reduce an instance to a smaller equivalent instance.

The appropriate method depends on input size, required accuracy, available time, structural properties, and whether optimality must be certified.