Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
577
questions
0
votes
1answer
27 views
Reduction from Clique to IS degree at most 4
This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks:
Edit:
And missing from the pic as @Nathaniel points out in his answer below:
"...
1
vote
1answer
67 views
How to prove NP-completeness of this mail-problem?
Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the ...
0
votes
1answer
21 views
Showing that a problem in $NP$ admits two distinct verifiers that satisfy additional constraints
Show that any $S \in NP$ has 2 different polynomial-time verifiers $V_1, V_2$ such that, for all $x,y$, the following conditions hold:
If $V_1(x,y)=1$ then $V_2(x,y)=0$
If $V_2(x,y)=1$ then $V_1(x,y)=...
0
votes
1answer
15 views
Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists
Below is Question 8.1 in Algorithms by Dasgupta et al.
There's a solution to this problem that uses binary search from here. Pasting the answer for posterity.
My questions are:
When they say input ...
1
vote
1answer
49 views
Any problem in P can be reduced to the language of odd integers
Given $A=\left\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\}$, we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$.
My attempt:
If $S \in P$ we can solve $S$ with a ...
-2
votes
2answers
80 views
Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)
Let me explain my trouble by another example.
The wiki page says that
Lattice problems are an example of NP-hard problems
However, by clicking NP-hard, i find this definition
A decision problem H ...
0
votes
1answer
20 views
Find a Cook Reduction from $R_{Clique}$ to its determinist problem
The question is to find Find a Cook Reduction from $R_{k-Clique}$ to its determinist problem.
Basically:
k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes.
...
-1
votes
1answer
28 views
Reduction from $VC$ to $CD$
We define the vertex cover as the problem of finding for a graph $G$, a cover of size $k$. A cover is a set of vertices such that every vertex has an edge to this set. We define CD (cycles destructor),...
0
votes
1answer
32 views
Why is crossing paths bad in Traveling Salesman?
I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths&...
4
votes
3answers
180 views
Algorithm for solving a mixed integer programming problem in polynomial time?
I have the following mixed integer programming (MIP) problem:
$$
\begin{array}{rll}
\text{Maximize } & z=k \\
\text{subject to }
& a_ik - m_i \geq 0 & (i=1,\dots,n) \\
& b_ik - m_i \...
2
votes
0answers
60 views
P/NP - Proof that SAT-TM is NP-complete uses certificate
To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard
$$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$
my ...
4
votes
1answer
79 views
Proof that $P\subseteq NP$ without nondeterministic TM
I know the proof that using nondeterministic TM, but as I understood there is another proof without nondeterministic TM.
If you answer please write with as much details as you can.
1
vote
0answers
52 views
any hope to solve np hard problem using deep learning? [duplicate]
I know some basic machine learning and deep learning. Now a days deep learning solve many types of problem. I working working optimization problem like np, np hard problem. Is there any hope to solve ...
0
votes
0answers
23 views
Reducing co-NP and NP. (Karp and Turing)
Why is it true that: If every problem in co-NP can be Karp reduced to a problem A, every problem in NP can be Turing reduced to A?
2
votes
1answer
38 views
Clarifying the definition of reduction with regards to NP-complete problems
In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
1
vote
1answer
69 views
show that NP is a subset of decidable languages
More specifically the problem says: "Let us call the set of decidable languages D. Show that NP ⊆ D"
My problem is that I always assumed that NP is decidable, but to prove it, I never ...
2
votes
2answers
76 views
Find maximal clique consisting of at least half of the vertices
Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority ...
2
votes
1answer
54 views
Difficulties proving when a language is in P or is NP-complete
I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$:
$L_1 = \{...
2
votes
1answer
107 views
Language Containment of Automata
If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?
0
votes
1answer
30 views
maximum Hamilton cycle and NP-completeness
we know max tsp (maximal Hamilton cycle) is NP-Hard. is there any decision version for this problem to conclude this is NP-Complete?
0
votes
0answers
55 views
Is the Maximum Independent Set problem NP-complete? [duplicate]
It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete?
This article says:
"Thus, the Maximum Clique Problem(MCP) and the Maximum Independent
Set(MIS) Problem are ...
1
vote
0answers
40 views
Show that if $P=NP$ then there is an algorithm that finds a witness for the language $L = \{x | \exists_w M(x,w)=1 \}$
Let $M(x,w)$ be a polynomial Turing machine with $|w| = poly(|x|)$, and $L = \{x | \exists_w M(x,w)=1 \}$.
Assuming that $P=NP$ I want to show that there is a polynomial algorithm $N(x)$ that finds a ...
1
vote
2answers
53 views
What is a certificate in plain english?
I've got this question from a course:
Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.
And it seems like this ...
0
votes
0answers
31 views
How can I prove the following problem is NP?
Because of the covid-19 pandemic, our firm works semi-remote working. We want to that:
Every day 2/5 of staff should be in the office.
Everyone should go to the office 2 times a week.
Teams want to ...
2
votes
1answer
327 views
The situation when P is a superset of NP
Could it be that three languages $A, B, C$ such that $A \subset B \subset C$, and $B \in P$, but $A$ and $C$ are $NP$-complete?
1
vote
1answer
80 views
P≠NP, yet NP=co-NP
I know , if P = NP then it can easily be proven that P = NP = Co-NP. But I was wondering,
if we assume P≠ NP, also then can it be proven that, NP =co-NP??
0
votes
0answers
32 views
How can I show a problem is in the intersection of np and co-np using duality and Farkas-lemma?
Currently, I have a hard time to find out the solution to this problem:
Given a matrix $A \in Z^{m \times n}$, $b \in Z^m$, $c \in R^n$ and $\lambda \in R$. Is there $x \in R^n$ with $Ax \leq b$ and $...
0
votes
1answer
130 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 ...
2
votes
2answers
78 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
85 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
50 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
15 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 ...
-1
votes
1answer
54 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?
...
1
vote
0answers
117 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
16 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
19 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
55 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
25 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
208 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
24 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
56 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
302 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
161 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
27 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
39 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 ...
1
vote
1answer
101 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 ...
