# Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

1,607 questions
Filter by
Sorted by
Tagged with
35 views

### Is this problem in NP. And if so why hasn't anyone used a simple problem like this to disprove P=NP [closed]

Information- Algorithms, and you by definition cannot predict true randomness, this is a fact 2. True randomness does exist at the very foundations of matter statement- does P=NP. The answer is no. ...
24 views

### why doesn't 2SAT proof work on 3SAT

the title is quite literally my question ; why doesn't the 2sat formula work on the 3sat. I am kind of a dunce btw
26 views

34 views

### Let 3-COL-$K_4$-FREE be the decision problem that asks if a graph that doesn't contain $K_4$ admits a 3-coloring. Show that the problem is NP-complete

I'm kind of struggling with this excercise. The obvious thing to try is to show that 3-COL $\leq_p$ 3-COL-$K_4$-FREE ($\leq_p$ stands for polynomial reduction). It is clear that 3-COL-$K_4$-FREE is in ...
1 vote
75 views

### Parameterized intractability relation between split and chordal graphs

I am a research scholar currently working in computational complexity. I am working on a decision problem $P$ that is known to be W-hard parameterized by the solution size on split graphs. As split ...
1 vote
42 views

### Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete

Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete I can understand why the union and intersection of 2 NP-complete languages are true but for statement above ...
34 views

### Hardness of finding exactly two Hamiltonian cycles in a graph

$\newcommand{\nuSwap}{\nu\textsf{-swap}}$ Two Hamiltonian cycles are different if and only if there is at least one edge they do not share. Let $L$ consist of all graphs with exactly two Hamiltonian ...
1 vote
47 views

### Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?

Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k? Is it correct to say that it doesn't exist because clique is ...
37 views

### Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?

I was reading a bit about $NP$-problems and how it is widely assumed that $NP\neq co$-$NP$. This also implies that the complement of $NP$-complete problems are not in $NP$. What is known is that the ... 124 views

### Complexity of variant of 3-SAT

This post introduces a new variant of 3-SAT called EQUAL-3-SAT where the number of clause is same as number of variables, and it is shown to be NP-complete. I want to ask if the monotone version of ...
1 vote
140 views

194 views

### Is this path planning problem NP-complete?

Given N integers L1, L2, ... , Ln ,we have a robot that starts at (0,0) moves north on integer grid for L1 steps, then it either continues in its current direction or makes 90 degrees right turn then ...
85 views

### Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier

For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X a1x1 + a2x2 + ... + ...