Intereting Posts

Found an recursive identity (involving a continued fraction) for which some simplification is needed.
$3\times3$ linear system organization
Is there an explicit isomorphism between $L^\infty$ and $\ell^\infty$?
Derivation of chi-squared pdf with one degree of freedom from normal distribution pdf
Likelihood Function for the Uniform Density $(\theta, \theta+1)$
Proving Congruence Modulo
How to show that the Volterra operator is not normal
finding the limit $\lim\limits_{x \to \infty }(\frac{1}{e}(1+\frac{1}{x})^x)^x$
Proving that a complex set in open/closed/neither and bounded/not bounded
Modular Arithmetic – Pirate Problem
Topologies and manifolds
Summation of $\sum\limits_{n=1}^{\infty} \frac{x(x+1) \cdots (x+n-1)}{y(y+1) \cdots (y+n-1)}$
Regular expression 00 or 11 not both
Proving an 'obvious' Ramsey upperbound
Parametric form of an ellipse given by $ax^2 + by^2 + cxy = d$

I am not really sure I understand the idea behind **Cook theorem** (it says that SAT is a NP-complete problem).

I read the proof with all its parts corresponding to the Turing machine TM solving it (TM is in a single state at any given time, only single cell is read by the head of TM in every single moment, only single symbol is on the tape etc…) + the fact that SAT is in NP (which is obvious)

… but I just dont understand how does it all prove anything?

- How can we show that 3-dimensional matching $\le_p$ exact cover?
- Confusion related to the definition of NP problems
- What are NP-complete problems and why are they so important?
- A graph problem
- For two problems A and B, if A is in P, then A is reducible to B?
- Solving SAT by converting to disjunctive normal form

The definition of NP-complete problem is, that a problem $U$ is in NPC, if all NP problems are polynomially reducible to $U$ and $U$ is in NP.

I understand that I can prove that some problem $V$ is in NPC, if I find another problem $W$ in NPC which is reducible to $V$ and check that $V$ is in NP (otherwise, it would be NP-hard, right?) so I basically need at least one problem to be known as NPC so I can begin with the reductions to other problems (and this problem is SAT as a root of this proof tree).

How does the long proof based on the work of TM actually prove that SAT is NPC? I cant posiibly prove that all NP problems can be reduced to SAT in this way, or can I?

- Why can't reachability be expressed in first order logic?
- A graph problem
- Can all theorems of $\sf ZFC$ about the natural numbers be proven in $\sf ZF$?
- Is the negation of the Gödel sentence always unprovable too?
- Learning how to prove that a function can't proved total?
- Ideas about Proofs
- Can every proof by contradiction also be shown without contradiction?
- Double Negation is sequent calculus systems LK and LJ
- Solving SAT by converting to disjunctive normal form
- Is Godel's modified liar an illogical statement?

A language $L$ is “NP-complete” if $L$ belongs to NP, and *every* language $X$ in NP can be polynomial-time reduced to $L$; that is the definition of “NP-complete”.

How might we show that *every* problem $X$ in NP can be reduced to $L$?

Well, $X$ is in NP, and the only thing we have to work with here is the definition of NP:

There is a nondeterministic Turing machine $M$ which,

given a string $I$,

correctly decides in polynomial time

whether $I$ is in $X$.

Cook’s theorem takes $M$ and a specific $I$ and constructs a large (but polynomial) family of statements that are satisfiable if, and only if, $M$ will accept $I$.

**The statements do this because they completely describe the exact computation that $M$ would perform starting with string $I$, including an assertion that $M$ would end in an accepting state.**

Because of the way the statements are constructed, they can be satisfied if, and only if, $M$ would *actually* perform a computation that ends by accepting $I$.

If there is no such computation, the clauses are not satisfiable.

So we have this large (but polynomial) family of statements which are satisfiable if, and only if, the machine $M$, which correctly recognizes the language $X$, would accept the particular string $I$.

If we had a satisfying assignment for those statements, that satisfying assignment would exactly describe what $M$ would do in accepting $I$: it would say how $M$ would move its head, and how it would modify the tape over time, and so on, and it would also describe the fact that $M$ would terminate in an accepting state.

So if we could find a satisfying assignment for this large family of statements, we would know that $I$ was in $X$, because we would have a complete description of how the machine $M$, which recognizes $X$, would behave in accepting $I$.

If we could *quickly* find a satisfying assignment for this large (but polynomial) family of statements, we would be able to quickly decide whether any given $I$ was in $X$, as follows: We would take the string $I$. We would construct the large (but polynomial) family of statements that collectively describe $M$’s computation starting with $I$, including the assertion that $M$ would end in an accepting state. We would quickly check if those statements were satisfiable. If they were, we would know that $M$ would accept $I$; if not then not.

But if we could quickly find satisfying assignments, we could quickly solve *every* problem $X$ that is in NP, because for *every* such problem $X$ there is a machine $M$ that recognizes $X$. So an efficient solution to the satisfiability problem would give us an efficient solution to problem $X$ that was in NP. If $X$ is in NP, there is some machine $M$ that recognizes it, and then given any string $I$, we could do just as in the previous paragraph to quickly decide whether $I$ was in $X$.

So an efficient method for finding satisfying assignments can solve efficiently solve *any* problem $X$ in NP:

Take the machine $M$ that recognizes $X$, construct a set of statements that describe its computation starting from $I$, including the assertion that the computation would end in an accepting state, and then check if those statements can be satisfied. If so, then $I$ is in $X$.

I hope that was some help.

Since $\mathrm{SAT}$ is the first problem proven to be NP-complete, Cook proved that $\mathrm{SAT}$ is NP-complete using the *basic* definition of NP-completeness which says that to prove that a problem is NP-complete if all NP problems are reducible to it in polynomial time. So, Cook did this using the Turing Machine concept.

After Cook’s work, life is made “easier”. To prove that a problem is NP-complete you only need to find an NP-hard problem and reduce it to your problem then prove that your problem is in NP to get the NP-completeness for your problem.

Look at Richard Karp’s paper to see how the reductions of a bench of problems work and how Karp did to prove that some problems are NP-complete based on reduction from $\mathrm{SAT}$.

I hope this helps.

- Dense board with sparse rook attacking
- How to prove $\sum^n_{i=1} \frac{1}{i(i+1)} = \frac{n}{n+1}$?
- Are elementary and generalized hypergeometric functions sufficient to express all algebraic numbers?
- Equilibrium existence proof
- Help proving the primitive roots of unity are dense in the unit circle.
- Expected Value of Matches Played Between Two Teams
- Prove The Orthogonal Complement of an Intersection is the Sum of Orthogonal Complements
- How much do we really care about Riemann integration compared to Lebesgue integration?
- prove that $gcd(f_m, f_n) = f_{gcd(n, m)}$, where $f_n$ is the nth Fibonacci number.
- A contradiction involving derivative
- Properties of Haar measure
- What is the basis for a proof?
- Handbook of mathematical drawing?
- Proving a trig infinite sum using integration
- Compute the minimum distance between the centre to the curve $xy=4$.