Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
620
questions
0
votes
0answers
7 views
What wold a NP reduction look like?
From my theory of computation lecture I recall:
If $A \le_m B$ and $B$ is decidable then $A$ is decidable (uses a computable function as a reduction).
If $A \le_p B$ and $B$ is in $P$ then $A$ is in ...
3
votes
0answers
27 views
Reduction from Edge-Coloring and Vertex-Coloring to a new problem
I have a question from a test I did and failed, a question I failed to do.
In short:
the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined.
The new ...
0
votes
1answer
58 views
Reduction from problem A to another problem B
I have a question from a test that I failed to pass, I failed to do the question.
The question:
Let A and B have two languages so that there is a reduction function f: $A\leq _pB$.
Suppose that $A \in ...
1
vote
2answers
44 views
Reduction between CLIQUE to SUBSET SUM
I have a question from a test that I failed to pass, I failed to do the question.
The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
2
votes
1answer
34 views
Reduction from language in P to another language in NP
I have a question I was unable to do, from a last test I had.
This is the question:
Will be $A \in NP$
Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
4
votes
1answer
69 views
+50
Reduction from the SAT problem to the NAE-SAT problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
0
votes
1answer
15 views
Reduction from the Clique problem to the Odd Clique problem
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question:
Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
30 views
Complications of a language that reaches a state of reject
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question
Let's look at the language $L_\mathrm{reject} = ${
$\left \langle M,w \right \...
-1
votes
1answer
31 views
Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u}
How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below?
input : a weighted graph $G$ and numbers $l$ and $u$.
output : Does $G$ has spanning tree, $S$, such that $...
3
votes
2answers
102 views
+50
tautology vs satisfiability
I had a test that I failed to pass, and it had a question that I failed to do.
This is the question:
Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
2
votes
1answer
64 views
Reduction from TSP to even TSP
I have a question from a test that I failed to pass, I failed to do the question.
The question:
Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight ...
2
votes
1answer
60 views
Complexity of the language that enters an infinite loop
A few days ago I had a test that I failed to pass, and it had a question that I failed to do.
This is the question
Let's look at the language $L_\mathrm{loop} = ${
$\left \langle M,w \right \rangle$ | ...
3
votes
2answers
199 views
Relationship between complexity classes W[1] and NP?
I am trying to understand the connection between The W-hierarchy as presented in chapter 13 of this book by Cygan et al. and the notion of the NP problems.
Is the existence of an FPT algorithm for a ...
1
vote
1answer
19 views
Relationship between NP and CoNP
I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question
This is the question
Will be $A\in NP$
Suppose that $A\notin CoNP$. ...
3
votes
2answers
47 views
Reduction with CoNP and CoNPC
I have a question I was unable to do, from a last test I had.
This is the question:
Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$.
Determine ...
0
votes
0answers
23 views
Reduction between p np conp [closed]
Hello everyone I am new here on the site, I had a test a few days ago that I failed, and there was this question that I could not understand.
Given:
Question 1
Suppose there is a reduction . ...
0
votes
1answer
25 views
How to know if language is in comp or np?
I'm new to the site.
I had a test a few days ago and failed it, I had a question I did not understand.
This is the question:
Let's look at the FALSE language: Collect all the verses P in the form of ...
1
vote
1answer
23 views
Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$
Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges.
I ...
1
vote
1answer
33 views
Why this problem is NP-Hard?
I'm asking about the question described here:
Knapsack Problem with exact required item number constraint
Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
-2
votes
0answers
139 views
Is there exist FPT algorithm for a variant of VC problem?
In CLOSED VERTEX COVER, we are given a graph $G$ where each vertex $v \in V(G)$ has self-utility $u_{v} \in \mathbb{N}$ and self-pollution $p_{v} \in \mathbb{N}$, and $k, U^{\star}, P^{\star} \in \...
0
votes
1answer
40 views
How to prove Dense Subgraph problem is in NP
I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies ...
1
vote
1answer
20 views
NP problem: certificate concept clarification
When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c&...
2
votes
0answers
29 views
How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?
Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get?
So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
3
votes
0answers
38 views
NP-complete problem
Is the following line true?
Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$
and $B$ is NP-complete problem, then $C$ is also NP-complete.
If B is NP-complete, then C would ...
0
votes
1answer
37 views
NP Reduction - Dominating set to SAT
Given a graph G and an integer k , recognize whether G contains dominating set X with no more than k vertices. And that is by finding a propositional formula ϕG,k that is only satisfiable if and only ...
2
votes
1answer
43 views
Does $NP^{SAT}=NP^{NP}$?
Does $NP^{SAT}=NP^{NP}$?
We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$.
But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?
2
votes
3answers
90 views
Easy proof for $Primes \in NP$
I want to show that $Primes \in NP$ an I've seen multiple proofs that use facts from number theory, like this one.
But isn't it much easier to proof
$$Composites=\{x\in \mathbb{N}\cup\{0\}:x=1 \vee\...
1
vote
1answer
25 views
If $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?
Is it true that if $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?
I couldn't find any answer to that question.
My attempt at proving it:
If $S\in\left(NP\bigcup coNP\right)$, ...
1
vote
1answer
40 views
polynomial reduction within Np
If $A \le_p B$ and $B\in NP$, does it necessarily follow that $A\in NP$?
($\le_p$ is a polynomial many-one reduction)
A quick yes/no comment is enough, a proof would be nice :-)
2
votes
1answer
26 views
Language in $R \setminus \mathit{NP}$
I am wondering whether the language $$L_{\textrm{hanoi}} = \{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\}$$ is in $R\setminus \mathit{NP}$.
I want to ...
0
votes
1answer
69 views
Assume P != NP, are these assertions valid?
Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$.
Are the following assertions valid?
$A \le_{P} B$
$B \le_{P} A$
My approach:
$B \le_{P} A$ isn't valid, ...
-1
votes
1answer
42 views
Are the following assertions true if P != NP?
We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold:
$MST^* \le_{P} ...
2
votes
1answer
43 views
Is quadratic nonresiduosity in $\textbf{NP}$?
The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
0
votes
2answers
94 views
How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem
Task:
A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, ...
0
votes
2answers
40 views
Is every problem with an output's size that grows polynomialy np?
I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$?
My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic ...
1
vote
1answer
27 views
Non-brute force algorithm for a Eulerian like path
I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one ...
0
votes
1answer
35 views
Karp's reduction strategy
One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction):
$$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&...
4
votes
4answers
3k views
Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?
I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
0
votes
1answer
110 views
Color coding to get an FPT algoirthm for k disjoint triangles
The k-disjoint triangles problem is as follows:
Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?
An FPT algorithm is presented here
(...
1
vote
2answers
49 views
Proving a problem is NP Hard
Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted ...
0
votes
1answer
50 views
IS SUBSET-SUM in P if b(the sum) is given in unary and a1,…,an is in binary?
The SUBSET SUM decision problem consists of poitive integers a1,...,an; b.
We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$
I want to prove that if b is given in unary(...
2
votes
1answer
80 views
How can I prove the following problem is NP complete?
The problem:
I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\...
0
votes
1answer
19 views
Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?
Here’s the decision problem:
Suppose I have N positive integers encoded in base-2 (as oppose to unary)
Are these integers precisely the integers 1-N in some order?
This is related to the Hamiltonian ...
0
votes
1answer
26 views
Are problems that are fractions of constraints of NP-complete problems also NP-complete?
We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes,
is ...
1
vote
0answers
14 views
What is the difference between NP and co-NP? [duplicate]
I'm trying to understand the very simple concept of co-NP but I can't figure it out. On wikipedia, it gives the example of SAT and its complement:
The complement of any problem in NP is a problem in ...
0
votes
0answers
30 views
If a problem A has a poly-time reduction to a problem B in co-NP, is A in co-NP as well?
i.e. $A\leq_pB\:\wedge\:B\in\text{co-NP}\rightarrow A\in\text{co-NP}$ ?
I feel like it's the case but I can't think of a straightforward proof.
Clarification: I am talking about polynomial-time Turing ...
0
votes
1answer
54 views
If P = NP, do these NP-complete problems reduce to these specific easier versions?
I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al.
Chapter 8 has the table below and I am wondering:
if $P = NP$ does each of the problems on the left reduce ...
0
votes
1answer
37 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
75 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
26 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)=...
