56

There are a bunch of teddy bears A, B, C, D and so on that are red on one side and blue on the other! (You choose how to color them) AND there are a bunch of 3 armed aliens with really long arms. Each alien grabs 3 teddy bear hands! (A teddy bear hand can be grabbed by more than one alien.) 3-SAT is the problem of whether you can color the teddy bears ...


39

Unfortunately, the original proof that Ramsey numbers exist (as in, are finite) was non-constructive, so mathematicians have been fighting an uphill battle from the beginning. Consider the diagonal Ramsey numbers $R(s, s)$. The smallest of these which remains unknown is $R(5, 5)$, so let's say we suspect $R(5, 5) = 43$—the current lower bound. We would ...


20

It doesn't work because it doesn't work. Say you have $W=10$ and there are three kinds of objects: Type $A$ has weight 9 and value 90. Type $B$ has weight 2 and value 19. Type $C$ has weight 1 and value 1. If you look at $v/w$, type $A$ wins, so you take one type $A$ object and fill up the remaining space with one type $C$, for total value $91$. But the ...


17

NP completeness means exactly that "all other NP problems could be reduced [in polynomial time] to the one", so yes, if a single NP-complete problem has a polynomial-time solution, then all NP problems do. See the formal definition. Note that it is not obvious that NP-complete problems exist in the first place! E.g. maybe for every NP problem A, I can find ...


15

It is currently unknown whether $P = NP$. All purported proofs have either been shown to be faulty, are under review, or are dismissed by the community at large without being considered. For more information on the last one, you might want to read Scott Aaronson's blog post detailing indicators why a purported proof is likely to be wrong and won't ...


13

If you could decide SAT problems in polynomial time, then you could also find a solution (for those instances that have them) in polynomial time. Namely, if Boolean expression $A$ is satisfiable and $x$ is a variable appearing in $A$, choose one of the expressions $A|_{x=T}$ and $A|_{x=F}$ (obtained by setting $x$ to "true" or "false" respectively) that is ...


12

The 9x9 board cannot be NP-complete, because there are finitely many instances of the problem.


10

Rather than strict NP-completeness, what I think what you're trying to ask is whether there is a transition similar to the one between 3-SAT and 2-SAT where the problem goes from being NP-hard to easy and in P. There is such a transition, but 9x9 Sudoku is on the wrong side of it. Solving a Sudoku puzzle is equivalent to deciding whether there is a valid ...


9

Actually, the classical NP-complete "vertex cover" problem is the decision problem: given natural number $k$ and graph $G$, is there a vertex cover of size $\le k$? If you could solve this problem in polynomial time, you could also find a cover of minimal size in polynomial time. The point is that given a vertex $v$, there is a vertex cover of size $k$ ...


8

there is some confusion in the question showing a lack of some basic understanding of the theory of NP completeness which is well documented in many places. particularly in this question: Is there any problem that been proven to be in NP? yes all NP complete problems are in NP. there are hundreds, maybe thousands of NP complete problems and minor ...


8

What would be if I be able to prove that one of the NP-Complete problems cannot be solved in polynomial time. I assume you mean "problems cannot be solved in polynomial time on a deterministic Turing machine". NP, after all, stands for "nondeterministic polynomial", and includes the decision problems that can be solved in polynomial time on a ...


8

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 ...


7

Yes, at our current state of knowledge it is certainly conceivable that P=NP is independent of any given axiomatic foundation for mathematics (such as Peano Arithmetic or ZFC). It might even be "independent of the axioms, but not provably so". In contrast to some other enigmatic sentences, knowing that P=NP is independent of the axioms would not in itself ...


7

A language is in NP if a proposed solution can be verified in polynomial time. In this case a proposed solution is simply a listing of the vertices in the order they appear in the claimed cycle. This list is the so-called certificate. To check if this list is actually a solution to the Hamiltonian cycle problem, one counts the vertices to make sure they ...


6

THE SHORT VERSION 3-SAT is basically a bunch of questions separated into groups of threes. If at least one in each group is true, we say it is satisfiable. If not, we say it's unsatisfiable. THE LONG VERSION AN EXAMPLE For example, we can think of things in the kitchen. We can look at 4 things; an oven, a microwave, a toaster, and a refrigerator. Now ...


6

My understanding of your first paragraph. To prove a decision problem $C$ [is NP-complete], 2 things need to be shown: There is a [polynomial-time] verification for [$C$'s] solution. It requires a polynomial-time verification, for the proof of $C$'s solution, as $C$'s "solution" is simply a yes/no. The proof of the decision is essentially the ...


6

Assuming for now on you deal with the decision problem of the TSP, which is: Given as input a weighted undirected graph $G=(V,E, \omega)$ and at bound $C$, is there a Hamiltonian cycle in G whose weight is at most C? This is easily seen to be in NP (contrary to the optimization version you state in your question, which, if shown to be in NP, would yield ...


6

Must an algorithm that decides a problem in NP also be able to construct a solution for that problem which can then be verified in polynomial time? No, but a solution can be easily derived using the decision procedure for NP problems because all "natural" NP-complete problems seem to be downward self-reducible and all NP problems can be reduced to NP-...


6

Yes. By definition any NP problem can be reduced to an NP-complete problem in polynomial time. Since NP-complete problems are themselves NP problems, all NP-complete problems can be reduced to each other in polynomial time.


6

Yes, many problems known to be NP are thought to be not NP-Complete. These include: Any problem in P, other than $\varnothing$ and $\Sigma^*$. (If these problems are NP-Complete, then $\text{P} = \text{NP}$.) Any problem known to be in $\text{NP} \cap \text{coNP}$ but not known to be in P, for example, integer factorization (converted to a decision problem)....


6

First, the article is reducing 3SAT to Max2SAT (not Max2SAT to 3SAT). In 3SAT, each clause has 3 variables and has the form $c_i=(l_1 \cup l_2 \cup l_3)$. For each clause $c_i$, create the following 10 clauses: $(l_1), (l_2), (l_3), (d_i), (\lnot l_1 \cup \lnot l_2), (\lnot l_2 \cup \lnot l_3), (\lnot l_1 \cup \lnot l_3), (l_1 \cup \lnot d_i), (l_2 \cup \...


6

3-coloring a graph is reducible to 10-coloring by a padding argument. Given a graph $G$ that you need to 3-color, create a new graph $H$ by adding the complete graph $K_7$ and making an edge from each of its vertices to all the vertices of $G$. The $K_7$ part of $H$ obviously cannot be colored with less than seven colors. None of those seven colors can be ...


5

This is a frequent source of confusion among people seeing NP for the first time. Let's see what the two definitions mean in the context of the Hamiltonian Circuit problem. HAMILTONIAN CIRCUIT: Given a description of a graph $G$ (perhaps by an adjacency matrix), is there a simple circuit in $G$ that contains all vertices of $G$? Definition 1 (verifying a ...


5

If you find a general algorithm that solves a single NP-complete problem in polynomial time, then you will have effectively proved that $P=NP$. Beware that solving one instance of a specific problem is not enough, you have to give an algorithm which solves any instances of the problem with any input data, and prove that the algorithm is polynomial in the ...


5

All of them. It's possible to verify if a proof is valid in polynomial time, and it's possible to check if the last step of a proof is the theorem under consideration in polynomial time, so just encode "valid proof of length N" as a satisfiability problem. N = 1 DO IF (there is a valid proof of length N that proves theorem T) THEN return TRUE IF (...


5

Yes. DNF and CNF formulas describe the solution space in different ways. DNF formulas are explicit in that they tell you exactly which assignments will satisfy the formula. CNF formulas are implicit in that they tell you what assignments won't satisfy the formula. Because DNF formulas are explicit, to determine satisfiability it suffices to go through ...


5

Every NP-complete problem is also a NP problem, by definition. Therefore, if NP=P, the same will be true for NP-complete problems. You can't say the same for NP-hard problems. These problems include all problems harder then NP problems, except for the NP-complete problems. In this case, we have that NP-hard $\cap $ NP = NP-complete. So, even if NP=P, we ...


5

The comments point out that $\rm P=NP$ "has to do with finite things". But formally speaking, it is a statement about the natural numbers. It is a first-order statement about the natural numbers. And in fact not a very complicated one. One can prove, quite easily once all the technical definitions had been understood, that the first-order theory of the ...


5

Yes, it comes up in OR (typically in references to problems being NP-complete or NP-hard). It is worth understanding, particularly in terms of understanding the limitations of what P versus NP versus not even NP (cannot be checked in polynomial time) means. The distinction is an asymptotic one (in terms of problem size). Too many papers use "it's NP-hard" ...


5

There is no polynomial-time procedure for deciding the satisfiability of 2-SAT + XOR-SAT unless P = NP. So, probably not. 2-SAT + XOR-SAT is easily proven NP-complete by direct polynomial reduction from 3-SAT. In a 3-SAT instance, each 3-CNF clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT + XOR-SAT expression $$(x_1 \lor \...


Only top voted, non community-wiki answers of a minimum length are eligible