Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
533
questions
0
votes
1answer
25 views
P vs NP characterization confusion
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in NP-Class.
(I mean, i think it is correct, but could ...
-1
votes
1answer
36 views
Need help to proof that NP⊆NP4
NP4 = { L | There exists a non deterministic polynomial Turing machine M, such that
for every x∈L, M accepts x on at least 4 paths in the computational tree of M on x.
and for every x∉L,M accepts x on ...
1
vote
1answer
30 views
algorithm for checking satisfiability
In order to prove that SAT is in NP, I need to come up with a polynomial time verfier (an algorithm). The Cooks Levin Theorem uses a non-deterministic Turing machine but that's not what I am looking ...
1
vote
0answers
25 views
are all problems in P in NP [duplicate]
I know this is a similar question to this post, but I want to further clarify my understanding.
In the picture from wikipedia:
I understand that every problem that's in $P$ is also in NP.
does this ...
0
votes
1answer
99 views
Is it incorrect too say that this function problem cannot be in $FNP$?
Decision Problem:
Is $2^k$ + $M$ NOT a prime?
$K$ and $M$ are our inputs represented as integers.
Function Variant: Output the result of $2^k$ + $m$
We can consider, $M$ = $0$.
Proof that calculating ...
-2
votes
1answer
68 views
Can an NP-Complete problem be reduced to an NP problem?
All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?
1
vote
0answers
17 views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP?
If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
0
votes
0answers
25 views
$NP$ is not in $P(n^k)$ for any fixed $k \geq 1$
I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$...
As an attempt, I thought of using the time hierarchy theorem which says that there ...
-1
votes
2answers
68 views
I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits?
Decision Problem: Given integers as inputs for $K$ and $M$. Is the sum of $2^k$ + $M$ a $prime$?
Verifier
...
1
vote
1answer
45 views
Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP
In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
0
votes
0answers
11 views
Does $L \leq_p K$ and $K\in NP$ implies $L \in NP$?
I only find theorems like $L \leq_p K$ and $K\in P$ implies $L \in P$ in books, but I think the same should be true for NP as well. Or is there anything I am missing?
I am asking since this would be ...
2
votes
3answers
65 views
Why isn't SAT in coNP?
I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).
But I'm missing why the following machine doesn't turing recognize the complementary of SAT:
Given a ...
0
votes
1answer
40 views
MAXSAT using dpll algorithm?
It's possible to return from a dpll algorithm M as maximum for MAX-SAT problem?:
I have a sample:
https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f
we can modify recurrency to return ...
0
votes
2answers
16 views
Proof of Co-Problem being in NP if Problem is in NP using negated output
Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof?
Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is ...
7
votes
1answer
246 views
Is the buckets of water problem in NP?
Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was ...
2
votes
1answer
177 views
Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset
I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
0
votes
1answer
27 views
Does P not NP imply NP COMPLETE disjoint from RP?
According to Wikipedia https://en.wikipedia.org/wiki/RP_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference?
Furthermore, am I correct that if this ...
0
votes
1answer
17 views
complexity of dividing set of number with constraints
I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.
There is a set of $n$ positive ...
0
votes
1answer
30 views
Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$
I'm having a small issue with wikipedia's proof that $RP \subseteq NP$:
An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
0
votes
1answer
74 views
“Given an algorithm, decide whether it runs in polynomial time” is this problem in NP?
This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).
However,...
-1
votes
2answers
52 views
How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?
How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?
OR
P = NP if NPC intersects with Co-NPC
0
votes
1answer
26 views
Why is the hitting set problem in NP
I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):
INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.
QUESTION: Does $S$ contains a ...
0
votes
0answers
16 views
Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?
Why this Question is False ?
NP-complete problems are the hardest problems in NP.
if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L].
Does this mean that L2 ...
3
votes
1answer
48 views
Complete resolution rule for 1-in-k SAT
In CNF SAT, each clause (A or B or C or...) must contain at least one true literal. The resolution rule applies to pair of clauses who have exactly one opposite literal.
(A or B or C) and (!A or D ...
0
votes
0answers
18 views
how to prove that $NP \cap co - NP$ = { S | S such that there exist a Strong Deciding Algorithm for S}?
i need to prove that and i find it struggle:
given:
for deciding problem S:
a non deterministic algorithm $A(x)$ is strong deciding algorithm if:
$x \in S =>$ fo every run of $A(x)$ returns "Yes"...
0
votes
0answers
105 views
Exact2IS - Question
I have the following question for Exact2IS problem that is defined:
$$ \mathrm{Exact2IS} = \{(G,k) \mid \text{$G$ contains exactly two independent sets of size $k$}\}. $$
and I would like to know ...
2
votes
1answer
128 views
Combining 2 problems in NP into one
Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$.
Can S be solved with oracle access to only one problem in $NP$?
...
0
votes
3answers
45 views
Is it possible that Co-NP = P but NP != P
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (...
4
votes
2answers
494 views
Can 3-coloring be reduced to 3-clique?
I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm ...
3
votes
1answer
88 views
Having trouble understanding a proof of Mahaney’s theorem
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.
I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $...
0
votes
1answer
53 views
Polynomial-time reduction of Primality and 3-SAT
Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.
Thank you.
1
vote
1answer
50 views
Reducing independent set to triangle-free subgraph
The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$.
An instance of the TFS (...
0
votes
1answer
31 views
Maximum number of positive literals in 2SAT
MAX 2SAT is NP complete.
Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (...
0
votes
0answers
32 views
How can I prove that the high-degree independent set problem is NP-hard?
I'm learning about NP Completeness, and I have come across the following problem
The decision-version of the high-degree independent set (henceforth "HDIS") problem is stated as follows: Given a ...
1
vote
1answer
60 views
P=NP when number of inputs that give 1 is bounded by polynomial
Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, ...
0
votes
0answers
18 views
the correctness of 2-satisfiability problem algorithm by using implication graph
I learned finding a solution of 2-sat problem algorithm below.
The point are below
(1) when constructing the implication graph
(2) finding there is no occurrence of a variable x and its negation x' ...
2
votes
0answers
25 views
Names of specific SAT variants
I enjoy reading research on satisfiability, but sometimes it's easier to find relevant information when you know the names of the variants.
Example:
All the clauses are width 3 and must have ...
1
vote
2answers
69 views
Are NP proofs limited to polynomial length?
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, ...
0
votes
0answers
28 views
Design of a single-tape NTM solving the TSP in $O({n}^4)$ time at most
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across a claim that a "single-tape NTM can ...
1
vote
0answers
54 views
CircuitSAT to 1-in-3SAT
This question follows
Unique 3SAT to Unique 1-in-3SAT
Consider an AND gate such that (A ∧ B) = C. It can be trivially expressed in 3SAT with 4 clauses and no extra variables.
$$
(A ∨ B ∨ \overline{...
1
vote
0answers
28 views
How to the NP hard of a problem that search for a subset of points with maximum scores?
Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1:
$[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$
Each point is assigned with a weight (possible negative):
$[w(...
0
votes
0answers
189 views
Witness finders
Given an NP language $L$, let a witness-finder for $L$ be a polynomial-time algorithm $M$ that
actually outputs a yes-witness $y$ for $x$ whenever $x \in L$, but could behave arbitrarily if $x \notin ...
2
votes
2answers
169 views
Unique 3SAT to Unique 1-in-3SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.
It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such ...
1
vote
1answer
27 views
Unique 1-in-3 SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.
I know the value of each bit of the unique assignment because it was made from a binary ...
1
vote
1answer
44 views
Karp reduction from optimization problems to decision problems
When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.
Focusing on Cook reductions, there exists a natural Karp ...
1
vote
1answer
27 views
One-way function is not injective when it is in NP
Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \...
1
vote
1answer
38 views
Independent set poly reducible to Strongly independent set?
A strongly independent set of a graph $G'$ is a subset $S$ of vertices such that the distance in $G'$ between every two distinct vertices in $S$ is larger than $2$.
It is possible to reduce an ...
0
votes
2answers
72 views
Is P contained in NP-hard?
I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.
NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained ...
0
votes
1answer
46 views
If a problem is complete for NP, is its complement complete for co-NP?
I am trying to prove that for a NP problem that is complete, its complement co-NP should be complete as well.
We know that a decision problem A $\in$ NP-complete if a) it is in NP and b) if every ...
3
votes
3answers
136 views
Has anyone seen a NP graph problem like this before?
I have a following graph-based problem:
Input: positive integers K and L, undirected graph G
I have to choose K vertices from this graph
In the path between each pair of chosen K vertices there ...
