The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
2answers
141 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
62 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
61 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 ...
-2
votes
0answers
23 views

Prove that VC (Vertex Cover) is in NP [duplicate]

I have this question in which it states that I have to prove whether Vertex Cover is in NP. I'm trying to understand my notes but the problem is that I do not know whether this is actually valid I ...
1
vote
1answer
63 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
34 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 ...
12
votes
1answer
154 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
40 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
63 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
133 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
276 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
32 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 ...
6
votes
1answer
448 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
128 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
62 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
57 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
140 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
113 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
96 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
53 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
68 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
109 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
66 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
109 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
116 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
130 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
156 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
129 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 ...
9
votes
1answer
147 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 ...
7
votes
4answers
159 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
-1
votes
1answer
111 views

Complexity classes that are closed under subtraction

Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't. Question was edited Original question: Im having some hard time figuring out what languages are closed ...
0
votes
1answer
238 views

Help reducing 3-SAT to 3-COLORING

I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part "Then for every variable xi that appears ...
2
votes
1answer
140 views

Is Co-NP closed under taking subset?

I have a question on my homework causing some confusion. If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False Now I understand what belonging to ...
1
vote
1answer
130 views

Prove the red blue separation problem is NP-complete

Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points ...
-3
votes
3answers
627 views

3-sat to 2-sat reduction

It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to P as there is known polynomial solution to it. So you can state that there is no such reduction from 3-SAT to ...
6
votes
1answer
47 views

Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP ...
0
votes
0answers
36 views

Help in developing a dynamic programming solution to this problem

I have asked this question on programmers.stackexchange but nobody was able to answer this question.I have asked for help on other forums but did not get much help.Since this is a part of my research ...
0
votes
3answers
224 views

Having trouble proving a language is NP-complete

I'm asked to prove that, if P=NP, that 0*1* is NP-complete, but I'm having trouble going about doing it. I know it's fairly easy to prove it's NP by creating a TM to verify an input (which can be done ...
3
votes
2answers
121 views

Problems in NP but not in #P

Are there problems that are in NP class but not in #P class? According to Wiki definition: More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number ...
2
votes
2answers
105 views

Direct reduction from Near-Clique to Clique

An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ ...
3
votes
2answers
83 views

What kind of NP problem would this be

I have N by N symmetrical matrix with each side having the same items. A B C D A 0 B 4 0 C 8 3 0 D 3 1 8 0 In reality ...
5
votes
1answer
104 views

One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP

Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$. But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using ...
0
votes
1answer
244 views

Showing that CLIQUE can be verified in polynomial time

The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is in NP and there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in ...
3
votes
2answers
139 views

Why is the difference of two NP-complete languages not in NP?

I found something in my notes I don't really understand, maybe you could help. Let $A$ = Independent Set and $B$ = Clique. Then, we clearly have $A \in \mathsf{NPC}$ and $B \in \mathsf{NP}$. Now, ...
4
votes
1answer
52 views

Max cut in cubic graphs

The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states A maximal cut of a cubic graph can be computed in polynomial time Browsing ...
1
vote
2answers
653 views

How to show that problems are in NP?

I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that ...
2
votes
2answers
369 views

Why NP is not closed under Turing reduction

The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine. For ...
3
votes
2answers
90 views

What is a Turing Machine in class coNP

On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...
3
votes
1answer
111 views

Is np-complete an equivalence class?

So, there are multiple possible definitions of "np-complete", two of which being: A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and $\forall L' \in \text{NP}: L' ...
2
votes
1answer
40 views

Showing filling a container with rectangles is hard by reducing from SUBSET-SUM

Given a set of rectangles, $D = \{ (a_1, b_1), (a_2, b_2) \dots , (a_n, b_n) \}$, where in each pair $(a_i, b_i)$, $a_i$ represents the height of the rectangle and $b_i$ the width, and given another ...