# Questions tagged [np]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

770 questions
Filter by
Sorted by
Tagged with
1 vote
34 views

• 161
33 views

### A decision procedure for PCP

I have read that the Post Correspondence Problem is undecidable. Let's say this is the problem of having a finite set of "dominoes" with a string in the top and another string on the bottom....
• 367
38 views

### Show that $PLANAR \in co-NP \cap NP$

The fact that the language of planar graphs is in $co-NP$ is easy to show because the complexity of finding a Kuratowski subgraph is $O(|V|)$. But what about $NP$? Any help is appreciated.
27 views

### How do you show that Cosmic Kite Problem is NP complete?

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
48 views

### NP-Hard version of TSP if P=NP

If P=NP (polynomial time algorithm for determining whether there exists a route smaller than L) would the NP-Hard version of TSP (finding the minimum distance route) still be NP-Hard? We would only ...
70 views

### Does $A^B = A^C$ imply $B = C$?

I am familiar with the Baker, Solovay, Gill result of non-relativization of P vs NP problem. They showed that $\exists A \text{ s.t }P^A \neq NP^A$. But since we are referring to $P, NP$ as models of ...
• 243
1 vote
23 views

### Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?

I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
1 vote
127 views

### Prove "Vertex Cover OR Clique" is NP complete

Instance: An undirected graph $G$ and a positive integer $k$ Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$? Obviously, this problem is solved by polynomial ...
1 vote
40 views

• 53
68 views

### if it were shown that every algorithm that solves SAT must have complexity Ω(n^(log n)) then P≠NP?

Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong? I can't find a formal proof
1 vote
179 views

6k views

### False proofs that look correct

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
1 vote
53 views

### P NP R RE closures

I wrote the following table for all the closures in those classes. is anything there incorrect? also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
• 53
1 vote
255 views

### is the class NP closed under set difference?

I know P is closed under all Boolean operations, but what about NP? is NP closed under set difference and symmetric difference? is this table accurate? Edit: updated table:
• 53
89 views

### Can all NP-complete problems be reduced to NP?

I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around? Can all NP-Complete be reduced to NP problems? My understanding is ...