The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
33 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 ...
2
votes
2answers
66 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
104 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
75 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
24 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, ...
2
votes
1answer
41 views

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

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 ...
1
vote
1answer
64 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
55 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
81 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
107 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
127 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
139 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
114 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
142 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
140 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
93 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
86 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
122 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
118 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
298 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
45 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
30 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
208 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
118 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
101 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
82 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
101 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
153 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 ...
-1
votes
1answer
75 views

Can anyone give a plain English explanation of the SAT problem? [closed]

I am new to algorithms. I Recently found the SAT problem. I tried to understand the Wikipedia article on it, but I couldn't understand much. Could someone explain what the problem is, and what is the ...
3
votes
2answers
128 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
49 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
307 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 ...
1
vote
2answers
280 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
68 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
87 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
38 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 ...
1
vote
1answer
668 views

Proving that if coNP $\neq$ NP then P $\neq$ NP

I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it. Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$. Show ...
2
votes
1answer
97 views

Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0. The problem is to ...
-1
votes
2answers
151 views

Wheel subgraph problem [duplicate]

In the following two threads I specified the question in the wrong way (easier to solve that way). Proving that finding wheel subgraphs is NP-complete Reducing from Hamiltonian Cycle problem to the ...
2
votes
1answer
774 views

Reduction from Vertex Cover to an Independent Set problem

Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim ...
1
vote
1answer
56 views

Vertex Cover problem modification

Modification of vertex cover problem. Given a graph G,does G have a vertex cover with 10 vertices? Is this problem still in NP? Given a graph G and integer k, does G have a vertex cover with k ...
0
votes
2answers
201 views

P is contained in NP ∩ Co-NP?

How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$? I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.
3
votes
1answer
49 views

Finding Hamiltonian cycles in polynomial space

Question: If $H = \{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\}$ ($m$ is in binary), prove that $H \in$ polynomial space. My thoughts: I thought that I could show that $H \in ...
0
votes
1answer
94 views

Show that this language is in NP $\cap$ coNP

Say $\ell: \{0,1\}^\ast \to \{0,1\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\{v \;\Big|\; \exists u: \bigl(u_1 = 1 ...
1
vote
3answers
130 views

k-path problem - P, NP or NPC?

I need to determine which complexity class this problem belongs to: Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two ...
4
votes
1answer
85 views

Prove that if $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$

Prove if a oracle machine $K$ is given with $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$. Lets assume that $\mathsf{P^k}=\mathsf{NP}$ then ...
1
vote
0answers
42 views

Do any decision problems exist outside NP and NP-Hard? [duplicate]

This question asks about a corner case of NP classes. From Wikipedia, NP is defined as: the set of all decision problems for which the instances where the answer is "yes" have efficiently ...
5
votes
2answers
163 views

A “natural” decidable problem not in $\mathsf{NP}$? [duplicate]

Are there any "natural" examples of decidable problems that are definitively known not to be in NP? The decidable languages I know of that are not contained in NP are usually derived from the time ...
6
votes
3answers
1k views

Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
2
votes
0answers
61 views

Karp reduction between FACTORING and a variant of it

Consider the following variant of the FACTORING problem (given N,M decide whether N has a prime factor less than M): MULTIPLE-FACTORING: Given three integers $1 \leq K \leq M \leq N$ decide if there ...