The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
34 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 ...
1
vote
0answers
21 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 ...
-4
votes
1answer
44 views

Proof problem is NP [on hold]

Hi need help to proof: For each A,B problems , if A ≤p B , and B ∈ NP then A ∈ NP Thanks.
0
votes
2answers
60 views

Tracking object problem

I have to track an object. I m confused whether its a P Problem or NP Problem?. The object is a piece of paper of white color, which matches with the background color I m working in, and also the ...
0
votes
1answer
24 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
36 views

Subset-Sum Problem Variant with Changing Target Sum - NP Complete?

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 ...
6
votes
2answers
83 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
36 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
43 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 ...
0
votes
0answers
24 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
23 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
23 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
79 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
235 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
192 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
75 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
158 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
69 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
32 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
54 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
73 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 ...
0
votes
0answers
60 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
169 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
78 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
80 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 ...
1
vote
1answer
89 views

Reduction to Maximum Independent Set

Suppose you had a set $P$ of people. Every person $p_j \in P$ is familiar with atleast one other person $p_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no ...
1
vote
1answer
67 views

if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$

I'm looking for a proof to the claim stated in the title: if $L\in NP\cap Co-NP$ is $NP$-Hard, then $NP=Co-NP$. I read the proof from my professor's recitation, but couldn't understand it, and I was ...
18
votes
2answers
237 views

NP-complete problems not “obviously” in NP

It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is ...
-1
votes
1answer
44 views

Is P^SAT subset of sum of NP and co-NP

I have a following problem: Let $P^{SAT}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle). Assume that: $co-NP \neq NP ...
1
vote
2answers
71 views

Do all decidable problems lie in the class NP?

All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a ...
4
votes
2answers
152 views

Is the complexity class NP computably enumerable?

The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing ...
1
vote
3answers
796 views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
3
votes
1answer
35 views

Minimum weighted arithmetic mean partion?

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$. I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean ...
7
votes
1answer
470 views

How do we know any problem is in NP-complete if we don't know all problems in NP?

A problem is NP-complete if: It is in NP. All problems in NP can reduce to it. It's number 2 that I'm concerned with here. I would be highly surprised if we knew every problem in NP. Based on ...
7
votes
1answer
137 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
4
votes
1answer
65 views

$NP\subseteq TIME[O(n^{\log n})]$

Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.
0
votes
1answer
79 views

NP Problem definition – verifiable on DFA vs. solvable on NFA

So in complexity theory, I've run across different definitions for NP problems -- Decision problems where a solution can be verified by a DFA in polynomial time Decision problems where a solution ...
1
vote
3answers
146 views

Why is SAT in NP?

I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?
1
vote
1answer
126 views

Is Wikipedia's formal definition of NP correct?

Wikipedia's formal definition of NP based on deterministic verifiers states: A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such ...
1
vote
2answers
122 views

Does a polynomial-time reduction from A to B imply that B is in NP if A is?

Let f be a polynomial-time reduction of a decision problem A to a decision problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then A $\in$ NP. However, what about the other ...
-1
votes
2answers
88 views

Proving that Max Weighted Independent Set is in NP

What I'm trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem I've chosen the max independent weight problem = input: A graph G with weights on each vertex, ...
6
votes
1answer
71 views

Why doesn't a time cutoff convert NP problems into co-NP? [duplicate]

Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations. You make a tweak to the verifier program, so that if it takes more than $f(n)$ ...
1
vote
1answer
130 views

Is this path finding problem in a 01-matrix NP-complete?

The problem: Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$) Output: YES if there exists a ...
1
vote
1answer
83 views

Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in ...
3
votes
1answer
125 views

Provability of NP /= P?

I'm a novice to the topic of provability so bear with me... During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an ...
4
votes
1answer
123 views

Existence of NP problems with complexity intermediate between P and NP-hard

Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete. I could ...
-1
votes
1answer
133 views

Is there a specific problem that is in both NP and co-NP but not in P?

A problem is in NP if a correct answer to it can be verified to be so in polynomial time. A problem is in co-NP if an incorrect answer to it can be verified to be so in polynomial time. P is a ...
1
vote
2answers
165 views

P vs NP: Assuming P = NP

Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$? I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, ...
1
vote
1answer
150 views

Is it true that all languages which have polynomial circuits are in PSPACE?

I just read about polynomial-size circuit families and I have a question as the title. I know P/poly is defined as the class PSIZE of languages that have polynomial-size circuits. But what about other ...
10
votes
1answer
159 views

Is this NP-hard? I cannot prove it.

I have a problem and I guess it NP-hard, but I cannot prove it. Here is a layer graph, where layer 0 is the hignest layer and layer L the lowest. there are some directed edge between layers, where ...