Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
553
questions
0
votes
0answers
36 views
Implications in $\mathbb{NP}$-completeness
Suppose I have an $\mathbb{NP}$-Complete problem called problem $A$. Further, suppose that $A$ is poly-time solvable in undirected-acyclic graphs; in other words, trees.
Now, If I take a problem ...
1
vote
0answers
21 views
Finding the common part of two systems of linear equations modulo 2
Given two systems of linear equations modulo 2, is there a method to find the common part (the equations which are true in both case) ?
For example...
Matrix 1: a⊕b=1 and c⊕d=0 and y=1 and e=0
Matrix ...
1
vote
1answer
79 views
Is NP in NP/Poly?
The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice ...
-3
votes
0answers
15 views
How can I create the table and solve the error, why did the error happened? [closed]
import world_population.csv
population = Table.with_columns(
"Population", population_amounts,
"Year", years
)
population
No module named 'world_population'
2
votes
2answers
59 views
proving that a problem is in P
I read online that this problem is in P:
Problem = {a^n, where n is a primary number}
I can't find any algorithm that decides if a word w in ...
0
votes
1answer
59 views
Proving NP-completeness for a not so cheesy problem
Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. ...
2
votes
0answers
42 views
Why do I only need to reduce from one problem in NP to prove NP-Hardness?
Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ?
Consider for instance the following situation:
Here, I have my set NP ...
1
vote
0answers
13 views
Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?
Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of ...
0
votes
1answer
36 views
If A is not in NP, and A reduces to B, does this mean B is not in NP?
I know it is true that if A is not in P, and A reduces B, then B is not in P.
But is it true for NP as well?
If A is not in NP, and A reduces to B, does this mean B is not in NP?
Why or why not?
...
0
votes
0answers
90 views
How to Show Subset Sum $\le_p$ 3-Partition
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete.
Is it ...
0
votes
0answers
15 views
Showing that Subset Sum Reduces to 3-Partition [duplicate]
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete.
This is a ...
1
vote
1answer
16 views
For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$?
Let $L$ be an $\mathrm{NP}$ language.
Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{*}$, $x \in L$ if and only if ...
0
votes
1answer
37 views
Proving the language of non-primes is in NP
I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.
Show the following language is in ...
0
votes
0answers
36 views
Are all reductions from NP-complete problems either NP-complete or are contained in P?
Let's say we have a problem $A \in \mathsf{NP}$. Now let's say we have a reduction $f(\mathsf{SAT}): A \leq \mathsf {SAT}$.
So, assuming that $A$ is not $\mathsf{NP}$-complete we have that $f(\mathsf{...
0
votes
0answers
21 views
Is there a decision problem in NP whose corresponding function problem is not in #P?
I am trying to get an imagination of the class #P for my bachelor thesis. Right now I think of it as a DTM that runs every possible path to run an algorithm on some decision problem at once. But in ...
1
vote
2answers
201 views
NP-completeness of testing whether a SAT formula does not contain any redundant clause
This paper explains that testing the irredundancy of a SAT instance is NP-complete.
But I don't understand the theorem/reduction.
How would one reduce 3SAT or k-SAT to this problem, for example?
1
vote
1answer
22 views
What is a good reference for NP hardness in the machine learning/optimization/operations research context?
I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:
Theorem 1.1. For any constant ϵ > 0, it is NP-hard ...
0
votes
1answer
34 views
If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?
This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?
Let's take the Traveling ...
1
vote
1answer
73 views
Why does SAT-UNSAT $\in NP \implies NP = coNP$
I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, ...
0
votes
1answer
32 views
Is it a sufficient condition to be in NP?
Suppose the following situation.
You have a decision problem $D$.
You know that $SAT$ is $NP$-complete.
You know that $D\leq_p SAT$.
Can you conclude that $D\in NP$?
I think it's true because it ...
4
votes
1answer
51 views
Can quantum computing help solve NP-Complete problems?
i was just wondering if quantum computing has done any good so far in solving NP complete problems.
I am aware that quantum computing does solve some NP problems which are classically hard in ...
0
votes
1answer
26 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 ...
2
votes
1answer
34 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
70 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
18 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
26 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
52 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
93 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
43 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
17 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
251 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
179 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
28 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
18 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
38 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
92 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
53 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
43 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
59 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
131 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
49 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
543 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 ...
