Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
762
questions
1
vote
1
answer
10
views
Prove "Vertex Cover OR Clique" is NP complete
Instance: An undirected graph $G$ and a positive integer $k$
Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$?
Obviously, this problem is solved by polynomial ...
1
vote
1
answer
35
views
$L_1\in P$ , $L_2\in NP$, is it possible that $L_1\cup L_2 \in P$
Prove\Disprove\Prove that equivalent to $NP=P$ or $NP\ne P$
given $L_1 \in P$ , $L_2 \in NP$ is $L_1 \cup L_2 \in P$?
Obviously $L_1 \cup L_2 \in NP$ because NP is closed under union and $P \subseteq ...
1
vote
1
answer
51
views
Proof that nondeterministic TM runs in exponential time
Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. ...
0
votes
1
answer
19
views
Two transition functions def of NP
I've seen a definition of NP alluded to in different texts where at each step an NDTM makes a nondeterministic choice between two transition functions and behaves accordingly. It seems like even in a ...
1
vote
0
answers
40
views
How could it be the case that NP != EXP? Do we know of any problems in EXP that are not in NP? [duplicate]
I know that NP is a subset of EXP, but I cannot find any resources talking about whether NP = EXP or not.
My intuition tells me that any problem that requires exponential time to be solved with a DTM ...
4
votes
0
answers
69
views
Extending Fagin's Theorem to the Polynomial Hierarchy
Fagin's Theorem (see Wikipedia and these lecture notes) states that there is an equivalence between second-order logic (SOL) formulas with existential quantifiers, and problems in NP.
I was wondering ...
0
votes
0
answers
16
views
Proof Closer String/Consensus String/Center String is NP-hard
Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
2
votes
0
answers
29
views
How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it.
Fur-
thermore, if a polynomial worst-case time ...
16
votes
4
answers
3k
views
Why is Integer Linear Programming in NP?
The decision version of the problem Integar Linear Programming is the following:
Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$.
Question: is there a ...
1
vote
1
answer
31
views
Subset ${\tt XOR}$ problem
Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation.
Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
1
vote
1
answer
43
views
Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?
The following problem has made me ask this question:
Given a boolean formula $\varphi(X)$ decide if there exists a quantification of $\varphi(X)$ with $k$ $\forall$ quantifiers that holds true. ...
1
vote
0
answers
40
views
Is $\mathsf P$ low for every complexity class between itself and $\mathsf{NP}$?
We know that $\mathsf P$ is low for itself. It's also low for $\mathsf{NP}$, $\mathsf{RP}$, $\mathsf{UP}$ and some other complexity classes that contain $\mathsf P$ and are contained in $\mathsf{NP}$. ...
0
votes
0
answers
25
views
Computational Learning Problem: 3-DNF Reduction
I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R
d and Y = {0, 1}. Consider the
class of Binary classifiers given by intersection of ...
-3
votes
1
answer
253
views
If Q* can break encryption would that prove P=NP?
At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
0
votes
1
answer
38
views
Pseudopolynomials and $NP$ problems like $CLIQUE$
Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be ...
0
votes
1
answer
30
views
Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?
$f$ and $g$ being known functions.
We suppose that the problem is solvable.
To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
2
votes
1
answer
58
views
Subset sum reducible to barter economy problem?
I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
0
votes
1
answer
52
views
Is the class NP closed under complement? (Follow-up)
As a follow up to this question already been asked here, I was wondering - if we supposed that P != NP, would then the following reasoning be correct:
In NP problems we can only verify in poly-time ...
0
votes
1
answer
87
views
Constructing an SAT formula from a Clique graph
We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand.
From my knowledge when ...
1
vote
1
answer
51
views
Why is infeasibility of linear programming considered to be an NP problem?
I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
19
votes
2
answers
4k
views
Why are computability problems always written in full caps?
Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
0
votes
0
answers
93
views
Is NP=RP(2^-n)?
I believe its true but struggle to prove.
I know NP=union over positive c's of RP(2^-(n^c))
and from here to prove that RP(1/2^n) contained in NP is immediate.
the other side is the problem.
I've ...
0
votes
1
answer
33
views
If I want to prove that a problem is in NP, can the vertifier use exponential space?
I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate ...
0
votes
0
answers
40
views
Investigating the Claim: co-$NP\subseteq NP\text{/}P$ implies $\Sigma_3^P=\Pi_3^P$ and Collapse of the Polynomial Hierarchy?
I have been studying the polynomial hierarchy recently, and I came across an intriguing claim that I would like to explore further:
Assuming co-$NP\subseteq NP\text{/}P$, the claim states that it ...
1
vote
1
answer
168
views
What could $P = NP$ imply about arbitrary Turing machines?
My question:
What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
0
votes
0
answers
42
views
SMALL-FACTOR is not NPC. Is the statement true or false?
Given the SMALL FACTOR problem where:
INPUT: an integer N and an integer k
OUTPUT: yes ⇐⇒ N has a prime factor ≤ k.
I know that SMALL-FACTOR problem ∈ in NP ∩ CO-NP.
If it were NP-Complete we would ...
1
vote
1
answer
50
views
What are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.
$VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
0
votes
0
answers
68
views
if it were shown that every algorithm that solves SAT must have complexity Ω(n^(log n)) then P≠NP?
Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong?
I can't find a formal proof
1
vote
0
answers
169
views
if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)
$L^\complement$ = the complement of L
is it true that if
$L\in NPComplete $
and
$L\leq_p L^\complement \rightarrow P=NP$
basically asking if the following statements are correct
$if (L\in NPComplete ) ...
2
votes
1
answer
99
views
How to provide a reduction from 3SAT to domatic number problem
How to provide a reduction from 3SAT to domatic number problem.
Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, ...
1
vote
1
answer
68
views
Hardness of the k-center problem with relaxed triangle inequality
Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle ...
25
votes
13
answers
6k
views
False proofs that look correct
I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful.
So, if anyone knows some common proof mistakes students make or some ...
0
votes
0
answers
21
views
reduction from partition to N3DM or balanced 3 partition problem
I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum.
N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
1
vote
1
answer
48
views
P NP R RE closures
I wrote the following table for all the closures in those classes.
is anything there incorrect?
also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
1
vote
1
answer
197
views
is the class NP closed under set difference?
I know P is closed under all Boolean operations, but what about NP?
is NP closed under set difference and symmetric difference?
is this table accurate?
Edit:
updated table:
0
votes
2
answers
86
views
Can all NP-complete problems be reduced to NP?
I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around?
Can all NP-Complete be reduced to NP problems?
My understanding is ...
0
votes
3
answers
110
views
If X is poly-time reducible to Y and X is in P, then Y is in P
The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
1
vote
0
answers
27
views
Class of optimization problems whose decision versions are in P
NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such ...
0
votes
0
answers
70
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
0
votes
0
answers
21
views
Construct polynomial-time algorithm to decide whether there is a linear classifier containing all points in X and no points in Y [duplicate]
Consider n-dimensional linear classifiers, that is, subsets of R n that have the form {(x1, x2, . . . , xn)| a1x1 + a2x2 + · · · + anxn ≥ b} for some real numbers a1, . . . , an and b. Given as input ...
0
votes
0
answers
18
views
Analogue of NP for oracle problems
I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems.
The ...
0
votes
1
answer
86
views
Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + ...
0
votes
0
answers
37
views
Is PrefixFreeNP=P?
I was given the following definition of a verifier:
Verifier $V$ is called $PrefixFree$ if for every $x,y$ such that $V(x,y)=1$, then for every $y'$ (which is not an empty string, $y'\ne\epsilon$) $V(...
4
votes
2
answers
111
views
Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)
Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true?
$A \leq_m$ B
$B \leq_m$ A
In other words, is there always a relationship between any two arbitrary NP-hard ...
0
votes
0
answers
21
views
$NP\subseteq P/poly\implies PH\subseteq P/poly$
We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
1
vote
1
answer
52
views
Do all P problems reduce to all NPI problems?
It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in ...
0
votes
1
answer
42
views
Do reductions (in NP and other classes) follow a linear path?
NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness.
There are other problems in NP that are also "equal" to one ...
2
votes
3
answers
154
views
Are there problems in NP that would solve P vs NP, but are not NP complete
NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is if we were to find some ...
0
votes
1
answer
99
views
Time complexity to convert a truth table to a boolean circuit
The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table?
But how about going the ...
1
vote
1
answer
32
views
I would like to know what are the directions to work on if I want to prove that $NP=coNP$?
I am currently learning about NP and coNP related content and have been exposed to the$NP \overset{\text{?}}{=}coNP$ problem.
I would like to know what are the directions to work on if I want to prove ...