Unit 14: More on Intractable Problems - Subjective Questions

NP-hard: A problem is NP-hard if every problem in can be polynomial-time reduced to it, written as . An NP-hard problem need not be a decision problem, need not belong to , and may even be undecidable.

NP-complete: A decision problem is NP-complete when:

• , meaning that a proposed solution can be verified in polynomial time.
• is NP-hard, meaning that every problem in reduces to in polynomial time.

Key distinction: Every NP-complete problem is NP-hard, but not every NP-hard problem is NP-complete. For example, the decision version of SAT is NP-complete, while the optimization version of the Traveling Salesperson Problem is NP-hard.

Examples of NP-complete decision problems:

• Boolean Satisfiability Problem (SAT)
• 3-SAT
• CLIQUE
• VERTEX COVER
• HAMILTONIAN CYCLE
• Decision version of Traveling Salesperson Problem
• SUBSET SUM

Examples of NP-hard problems:

• Optimization version of the Traveling Salesperson Problem
• Minimum set cover optimization
• Chromatic number computation
• Certain scheduling optimization problems
• The Halting Problem, which is undecidable

NP-complete problems must be decision problems in . NP-hard problems only need to be at least as hard as every problem in ; they do not have to belong to or even be decidable.

Cook's theorem, also called the Cook–Levin theorem, states that the Boolean Satisfiability Problem (SAT) is NP-complete.

The theorem establishes two facts:

• SAT belongs to : Given a truth assignment, one can evaluate the Boolean formula in polynomial time.
• SAT is NP-hard: Every problem in can be transformed into a SAT instance in polynomial time.

Importance:

• It identified the first NP-complete problem.
• It provided a starting point for proving thousands of other problems NP-complete through polynomial-time reductions.
• It connected nondeterministic polynomial-time computation with Boolean formulas.
• It showed that a polynomial-time algorithm for SAT would imply .

Let be any problem in . By definition, a nondeterministic Turing machine decides in polynomial time. Cook's theorem encodes the polynomial-length computation of on an input as a Boolean formula .

Variables represent information such as:

• The symbol stored in each tape cell at each time.
• The current state of .
• The position of the tape head.

Clauses enforce that:

• The initial configuration correctly represents .
• Every configuration legally follows from the preceding one.
• Exactly one state, symbol, and head position is selected where required.
• An accepting state is eventually reached.

The formula satisfies

Because the machine runs for polynomially many steps, the formula has polynomial size and can be constructed in polynomial time. Thus, every problem in reduces to SAT.

A polynomial-time many-one reduction from problem to problem , denoted , is a polynomial-time computable function such that

The function converts every instance of into one instance of while preserving the yes-or-no answer.

Role of reductions:

• If and has a polynomial-time algorithm, then also has a polynomial-time algorithm.
• If is NP-hard and , then is NP-hard.
• Reductions allow the difficulty of known problems to be transferred to new problems.
• They are the principal technique used to prove NP-completeness.

To prove that a new problem is NP-hard, one must reduce a known NP-hard problem to :

This direction shows that an efficient algorithm for could also solve efficiently. Therefore, is at least as hard as .

Showing proves only that is no harder than ; it does not establish that is NP-hard.

A useful rule is: reduce from the known hard problem to the new problem whose hardness is being proved. The reduction must also preserve answers in both directions:

Suppose through a polynomial-time function , and through a polynomial-time function . Then

Define the composed transformation as

Both and run in polynomial time, and the output produced by has polynomial size. Therefore, their composition also runs in polynomial time. Hence,

Usefulness: Transitivity permits chains of reductions. Once SAT is proved NP-complete, it can be reduced to 3-SAT, 3-SAT to CLIQUE, and CLIQUE to other problems. Each link transfers NP-hardness without requiring a direct reduction from every problem in .

The proof has two parts.

1. Show that 3-SAT belongs to :
Given a truth assignment, evaluate each clause and verify that all clauses are true. This requires time polynomial in the formula size.

2. Show that 3-SAT is NP-hard:
Reduce SAT to 3-SAT. First convert a Boolean formula into conjunctive normal form using a polynomial-size construction. Clauses are then transformed so that each contains exactly three literals.

For a long clause such as

introduce a fresh variable and replace it with

Similar padding handles clauses with fewer than three literals. The new formula is satisfiable exactly when the original formula is satisfiable, and its size is polynomial. Therefore, , so 3-SAT is NP-complete.

The CLIQUE problem asks: Given an undirected graph and an integer , does contain a set of at least vertices in which every pair is connected by an edge?

Membership in : A certificate is a set of vertices. One can check all vertex pairs in time to confirm that every required edge exists.

NP-hardness: A standard reduction is from 3-SAT. Create one vertex for each literal occurrence in every clause. Connect vertices from different clauses when their literals are not contradictory. If the formula has clauses, ask whether the graph has a clique of size .

A satisfying assignment permits one mutually consistent true literal to be chosen from each clause, forming a clique. Conversely, a clique of size selects one consistent literal from every clause and yields a satisfying assignment. Thus, 3-SAT reduces to CLIQUE in polynomial time.

For an undirected graph , its complement contains an edge exactly where does not contain one between two distinct vertices.

A set is a clique in if and only if is an independent set in . Also, a set is independent in a graph if and only if is a vertex cover.

Therefore,

if and only if

The complement graph and the new integer can be constructed in polynomial time. Hence,

Since CLIQUE is NP-complete and VERTEX COVER belongs to , this relationship can be used to prove that VERTEX COVER is NP-complete.

The INDEPENDENT SET decision problem asks whether a graph contains at least vertices such that no two selected vertices are adjacent.

A set is independent if and only if its complement is a vertex cover:

• If is independent, no edge has both endpoints in . Thus every edge has at least one endpoint in .
• If is a vertex cover, no edge can have both endpoints outside the cover. Therefore, no two vertices in are adjacent.

Consequently,

if and only if

This gives polynomial-time reductions in both directions and shows that the decision problems have closely related computational difficulty.

The HAMILTONIAN CYCLE problem asks whether a graph contains a cycle that visits every vertex exactly once and returns to its starting vertex.

Membership in : A certificate is an ordering of all vertices. Verification checks that:

• Every vertex appears exactly once.
• Consecutive vertices are connected by edges.
• The last vertex is connected to the first.
  These checks take polynomial time.

NP-hardness: It can be established by a polynomial-time reduction from a known NP-complete problem such as 3-SAT. The graph is built with variable and clause gadgets. A Hamiltonian cycle must choose one of two paths through each variable gadget, representing true or false, and must visit every clause gadget through a path corresponding to a satisfied literal.

The construction guarantees that the graph has a Hamiltonian cycle if and only if the original formula is satisfiable. Thus, HAMILTONIAN CYCLE is both in and NP-hard.

Given cities and pairwise travel costs:

• The decision version asks whether there is a tour visiting every city exactly once, returning to the start, with total cost at most .
• The optimization version asks for a tour of minimum possible total cost.

The decision version belongs to because a proposed tour can be checked and its cost summed in polynomial time. It is also NP-hard, so it is NP-complete.

The optimization version is NP-hard. It is not classified as NP-complete because NP-completeness is defined for decision problems.

If the optimization version were solvable in polynomial time, the decision question could be answered by comparing the optimum cost with . Conversely, a polynomial-time decision algorithm can be used repeatedly with different bounds to determine the optimum when costs have polynomial-length encodings.

The SUBSET SUM problem is: Given integers and a target , determine whether there is a subset whose elements sum exactly to .

Formally, the question is whether some satisfies

Membership in : A certificate specifies the selected indices. Their values can be added and compared with in polynomial time.

NP-hardness: A polynomial-time reduction from a known NP-complete problem, such as 3-SAT, encodes variable choices and clause satisfaction as carefully positioned digits of integers. Selecting one number for each variable represents a truth assignment, while additional numbers ensure that the target can be reached exactly when every clause is satisfied.

Thus, SUBSET SUM is in and NP-hard, making it NP-complete.

In the -COLORABILITY decision problem, the input is a graph and an integer , and the question is whether every vertex can be assigned one of at most colors so that adjacent vertices receive different colors.

A proposed coloring can be verified by examining every edge, so the problem belongs to . For , -COLORABILITY is NP-complete. In particular, 3-COLORABILITY can be proved NP-hard through a reduction from 3-SAT using variable, clause, and consistency gadgets.

The optimization problem asks for the graph's chromatic number , the minimum number of colors required. Computing is NP-hard rather than NP-complete because it is an optimization problem.

The special case is tractable: a graph is 2-colorable exactly when it is bipartite, which can be tested using breadth-first or depth-first search.

In SET COVER, the input consists of a universe , a family of subsets whose union contains , and usually an integer .

The decision version asks whether at most subsets can be selected so that their union equals :

A proposed collection can be checked in polynomial time, so the decision problem belongs to . A reduction from a known NP-complete problem, such as VERTEX COVER, establishes NP-hardness. In that reduction, graph vertices correspond to selectable sets and graph edges correspond to universe elements that must be covered. Therefore, the decision version is NP-complete.

The optimization version asks for the smallest possible number of subsets and is NP-hard. Although exact polynomial-time algorithms are not known, greedy selection provides a logarithmic-factor approximation.

A certificate is additional information proposed as evidence that an input is a yes-instance. A polynomial-time verifier is a deterministic algorithm that checks input and certificate in time polynomial in .

A decision problem belongs to if there is a polynomial and a polynomial-time verifier such that

Examples include:

• A truth assignment for SAT.
• A set of vertices for CLIQUE or VERTEX COVER.
• A tour for the decision version of TSP.
• A selected subset for SUBSET SUM.

To prove that a problem is NP-complete, one must demonstrate such polynomial-time verification and separately prove NP-hardness through a suitable reduction.

A standard NP-completeness proof follows these steps:

1. State the decision problem precisely: Identify the input, the yes-or-no question, and any constraints.
2. Show membership in : Describe a polynomial-size certificate and a polynomial-time verification algorithm.
3. Choose a known NP-complete problem : Select one whose structure resembles the new problem .
4. Construct a polynomial-time transformation: Map every instance of to an instance of .
5. Prove forward correctness: Show that if is a yes-instance of , then is a yes-instance of .
6. Prove reverse correctness: Show that if is a yes-instance of , then is a yes-instance of .
7. Analyze complexity: Show that the construction takes polynomial time and produces an output of polynomial size.

These facts establish , so is NP-hard. Combined with , they prove that is NP-complete.

Suppose an NP-complete problem has a polynomial-time algorithm. Since every problem can be reduced to in polynomial time, an instance of could be transformed into an instance of and then solved efficiently. Therefore, every problem in would belong to .

Since is already known, this would imply

Consequences would include polynomial-time algorithms for SAT, CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE, SUBSET SUM, and many scheduling and routing decision problems.

Conversely, proving that even one NP-complete problem has no polynomial-time algorithm would establish

However, a fast algorithm for a special case, an approximation algorithm, a heuristic, or an exponential-time algorithm does not by itself resolve the versus question.

A numerical problem is weakly NP-complete when its hardness depends partly on large numerical values encoded compactly in binary. Such a problem may admit a pseudo-polynomial algorithm, whose running time is polynomial in the numeric values but not in the number of bits used to encode them.

For example, the dynamic-programming algorithm for SUBSET SUM runs in approximately time, where is the target. Since the binary representation of uses only bits, is not polynomial in the input length. SUBSET SUM is therefore weakly NP-complete.

A problem is strongly NP-complete if it remains NP-complete even when its numerical values are bounded by a polynomial in the input size. Such problems do not admit pseudo-polynomial algorithms unless . The 3-PARTITION problem is a standard strongly NP-complete example.

This distinction helps determine whether dynamic programming based on numeric magnitudes may provide an exact practical solution.