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
vote
1answer
49 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
24 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
45 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
142 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
97 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
38 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
45 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
60 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
154 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 ...
1
vote
3answers
117 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
59 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 ...
0
votes
1answer
80 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.
-3
votes
1answer
84 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
172 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
71 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
246 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
47 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
49 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 ...
17
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
49 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
15 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!
1
vote
0answers
37 views

Are there any known “hard” instances for NP-Complete Problems [closed]

Are there any known "hard" instances for NP-Complete Problems, or are there no general hard instances. So for different algorithms different instances are hard?
7
votes
1answer
181 views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
6
votes
1answer
32 views

Versions of NP with different logical unifiers

One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into ...
0
votes
1answer
68 views

Is this problem P or NP?

Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$? Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?
1
vote
1answer
37 views

IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why. First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a ...
2
votes
0answers
37 views

reduction of maxcut problem

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
-2
votes
1answer
50 views

Proof problem is NP [closed]

Hi need help to proof: For each A,B problems , if A ≤p B , and B ∈ NP then A ∈ NP Thanks.
1
vote
1answer
32 views

Reductions where the number of certificates from one problem can be computed for another to varying degrees

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases: (1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same ...
1
vote
0answers
51 views

Subset-Sum Problem Variant with Changing Target Sum - NP Complete? [closed]

Is the Subset-Sum Problem (SSP) with a changing target sum (which is dependent on the chosen subset) also NP-complete? If so, how would I reduce SSP to this or prove that it is NP-complete in another ...
8
votes
3answers
174 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
-1
votes
1answer
38 views

Proving that the set of non-universal CFGs is not in NP

How do I prove that $\overline{\mathrm{ALL_{CFG}}}$ does not fall in NP, where $\qquad\mathrm{ALL_{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^* \}$
0
votes
1answer
90 views

Problem A is polynomially reducible to problem B…what can we say about A and B?

This is a question on a practice final. Problem A is polynomially reducible to problem B. Which of the following statements is correct? I. If problem A is solvable in a polynomial time then problem ...
1
vote
0answers
26 views

Algorithms for verifying and solving three-coloring [duplicate]

I found the following problem that I am trying to answer: Consider the three color problem where V, vertex set of a bipartite graph. can be partitioned into three subsets such that there is no ...
3
votes
1answer
40 views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
2
votes
1answer
41 views

What is the implication of the sentence: “if any NP complete problem is p time solvable, then all problems in NP are p time solvable”

I find this quote here on page 13 Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p ...
4
votes
1answer
87 views

Why is Steiner Tree trivially in NP?

I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin NP. But I can't seem to wrap my head around this. Why is this so?
3
votes
2answers
244 views

Decision problem which belongs to P reduced to a decision problem which belongs to NP?

Is it possible to have a decision problem $A$ which belongs to P and reduce it to a decision problem $B$ which belongs to NP, i.e. $A \leq_{\mathrm{p}} B$, where $A$ belongs to P, $B$ belongs to NP?
-2
votes
3answers
214 views

Is every problem in NP solvable?

Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
0
votes
1answer
91 views

Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false? 1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$. True. Every finite set is in $P$ and ...
1
vote
1answer
174 views

Concatenation of languages in NP

I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my ...
0
votes
1answer
78 views

If P = NP, then is NP = FNP?

I read FP = FNP iff P = NP which makes sense. But if P = NP, does it mean FNP = NP? Intuitively, I think no because P = NP would mean that decision problems in NP would become decision ...
2
votes
1answer
33 views

Property of two ANEAs is in NP

I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A_1}$ and $\mathcal{A_2}$ and want to show that the problem $L(\mathcal{A_1}) \not \subseteq L(\mathcal{A_2})$ is in NP by ...
5
votes
1answer
58 views

Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

Assuming $\Sigma = \{ 0, 1\}$.. Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$? So it ...
4
votes
2answers
120 views

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to ...
2
votes
1answer
107 views

Homomorphism erasing information

I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under ...
5
votes
1answer
180 views

Why does the solution of an NP problem have to be polynomial size?

I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that ...
1
vote
2answers
96 views

NP-hardness of an optimization problem with real value

I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$. ...
0
votes
2answers
93 views

Execution time of NP and NP-Complete algorithms

For P algorithms, we say that the execution time can be logarithmic O(log n), lineal O(n), quadratic O(n^2), etc. For NP and NP-Complete algorithms is there a way to represent the execution time? Or ...