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

learn more… | top users | synonyms

-1
votes
1answer
32 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for ...
0
votes
0answers
34 views

What is an example of a problem that is in NP - P, but not NPC? [duplicate]

Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true. What is an example of a problem that is complex enough to be in ...
3
votes
1answer
74 views

Proof that this problem is in NP

I have to prove the following problem is in NP (and define verifier as well as the certificate/witness): The input is a set of $n$ boxes with weights $w_{1},\ldots,w_{n}$ and two numbers $s$ and $t$ ...
-1
votes
0answers
38 views

Conditions on randomized reductions

Supposing we have a problem $\Pi$. Suppose $\Pi$ has a randomized reduction from $\mathsf{3SAT}$ but there is no deterministic reduction then it is clear $\mathsf{NP}\neq\mathsf{P}$. My query is ...
4
votes
1answer
67 views

An obvious approach to explaining NP != coNP, how far has it been pushed?

A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking ...
2
votes
1answer
105 views

An obvious approach to NP = coNP, is there a counterexample?

Let's try to solve "co3SAT" with an NTM in polynomial time. It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction. We've got a formula in ...
0
votes
0answers
36 views

In computer science, is there a term that describes a solution set that is guaranteed to contain the solution to a NP hard problem?

Suppose that a NP hard problem involves finding a set $A$, and that there exists a polynomial time algorithm that is able to find a smallest set $B$ such that $A \subset B$. Occasionally, we might be ...
-2
votes
2answers
66 views

How to prove P ⊆ Co-NP

My approach Let L ∈ P $\exists$ Turing Machine $M_1$ which decides L. We can easily construct $M_2$ which decides $\bar{L}$ $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP I'm not sure ...
5
votes
1answer
54 views

Certificates and NP?

My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be. For instance, for SAT, ...
0
votes
0answers
20 views

Why does not the complement of a language belonging to class NP, also belong to NP in general? [duplicate]

I know that complement of a language belonging to NP, does not necessarily belong to NP. I came across the example $L= \{\langle G,s,t \rangle | G \text{ is a directed graph and there exists a ...
1
vote
1answer
64 views

NP to SAT. How does it works? [closed]

Let's start here: It is said that all NP problems can be reduced to SAT(boolean satisfiability problem). To be more accurate to Circuit SAT, because all decision problems like NP should end up with ...
2
votes
1answer
221 views

Why do puzzles like Masyu lie in NP?

The puzzle is made up of (n x n) squares so when taking the problem the input size would be n. Rules of Masyu: The goal is to draw a single continuous non-intersecting loop that properly passes ...
4
votes
2answers
382 views

Seems like NP cannot equal coNP by the definition of NP

A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will ...
6
votes
1answer
59 views

What NP decision problems are not self-reducible?

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...
11
votes
2answers
794 views

Is Post Correspondence Problem in NP?

I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input ...
0
votes
0answers
45 views

How to solve a problem that is even hard to approximate?

I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a ...
1
vote
1answer
54 views

How to prove membership of NP [duplicate]

My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're ...
6
votes
2answers
159 views

Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
4
votes
2answers
76 views

Can NP-Hard be converted to NP?

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem. Can an NP-Hard problem ...
4
votes
3answers
728 views

Evolving artificial neural networks for solving NP problems

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. ...
2
votes
2answers
99 views

Why is $P \subseteq NP$?

The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf However, Where does it come from that these are inclusive sets and not separate? Or that ...
-2
votes
1answer
44 views

Show that $L^c$ is also in NP

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below. L is in NP and for every n, there is exactly one string of length n that belongs ...
4
votes
0answers
95 views

If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?

I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure. Begin with $NP \subseteq BQP$ (*) $\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
1
vote
0answers
48 views

Complexity lower bounds via Cook reductions

Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information ...
1
vote
1answer
68 views

Half-SAT intractability proof

I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows: Half-SAT is a problem where C is a CNF boolean ...
10
votes
1answer
238 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
10
votes
1answer
309 views

Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
2
votes
1answer
98 views

How are these problem variants that ask about the size of optimal solutions in NP?

I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here. On page 5 (23 in the pdf), it says that the following decision problems are in NP: Is the ...
1
vote
1answer
90 views

NP Complete Subset GCD Proof

$SubsetGCD$ is described by the following: instance: A set of positive integers $S$ and an integer $k$ question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$ ...
0
votes
0answers
46 views

Is a crossword puzzle in NP? [duplicate]

I've given a problem about an abstract crossword puzzle: Given: We have a crossword puzzle with the dimensions $n \times n$ and a finite set of words $W \subset \Sigma^{\ast}$. Question: Is it ...
0
votes
0answers
26 views

How can I determine whether a problem is NP-Hard [duplicate]

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case? Suppose I have different groups of people m in a list M= {m1, m2} ...
1
vote
1answer
47 views

Do problems in P only reduce to NP and coNP problems?

Consider the languages $B,C,D$, such that $B\le_p C$ and $B\le_p D$. Statement: $B\in P, D\in NP, C\in coNP$. Is the statement true for every $B,C,D$? I know that the answer is no and I have ...
1
vote
1answer
195 views

If the decision problem can be solved in poly time, show the optimization problem also can [duplicate]

Here is a problem I am trying to solve: The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes ...
7
votes
1answer
127 views

Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
5
votes
1answer
45 views

Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints: Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then ...
3
votes
1answer
48 views

Proving NP completness without reductions

What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?
1
vote
1answer
100 views

Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?) [duplicate]

I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble. Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of ...
-1
votes
1answer
304 views

How to prove a Double CNF SAT is in NP [duplicate]

So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would ...
3
votes
3answers
169 views

Understanding definition of NP

In my lecture notes, the definition of the class NP is given as: A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that: For every input $x$, ...
-2
votes
1answer
83 views

If an NP problem reduces to an NPC problem, it is NPC?

Is the following statement true? If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete. Intuitively I think the answer is No because ...
1
vote
1answer
206 views

Does every problem in NP have an exponential time algorithm?

I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.
-2
votes
1answer
101 views

Which of these problems is not in NP? [closed]

I see one solved ex on Algorithms. Which of the following is in NP? Decision Version of TSP Array is Sorted? Finding the maximum flow network Decision version of 0/1 knapsack? ...
14
votes
3answers
198 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
1
vote
1answer
114 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
4
votes
1answer
249 views

Does NP-completeness require to find the solution?

In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem: Problem 2.1 (Clique). Given a graph $G = (V, E)$ and an integer $k$: if ...
4
votes
1answer
51 views

What is an $NP^{NP}$-complete problem? [duplicate]

So in this paper I'm reading (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. ...
1
vote
1answer
63 views

How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

How can TSP be an NP-optimization problem ? The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and ...
18
votes
3answers
1k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
3
votes
1answer
100 views

Pseudo polynominal time algorithm for Np-Complete Problems

For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don't we have then a ...
0
votes
0answers
16 views

Subexponential algorithm for Np-complete problems [duplicate]

http://cstheory.stackexchange.com/a/3627/32204 Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!