Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
645
questions
2
votes
3answers
86 views
Proving that a class equals NP ∩ coNP
We say that a non-deterministic Turing machine is nice if for every input x the following holds:
• Every computation path returns either ’accept’, ’reject’ or ’quit’.
• There is at least one non-quit ...
5
votes
1answer
481 views
Why are $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ compatible?
If $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ are both true then $\sf{P}$, $\sf{NP}$ and $\sf{coNP}$ are three separate complexity classes. In other words, verifying a solution, finding a ...
0
votes
2answers
72 views
Can we DISPROVE that a problem is NP-complete
So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
6
votes
1answer
110 views
Prove TILING is NP-Complete
I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, ...
1
vote
1answer
32 views
A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?
if A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial
time solvable then is B is polynomial time solvable?
on the contrary, if A be an NP-complete problem, and B be an NP-...
3
votes
1answer
81 views
How is the time complexity of a non-deterministic Turing machine defined?
I read different things online about this:
In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n.
So this is only ...
0
votes
0answers
20 views
Strategy to reduce between decision problems
I'm very new to complexity theory, please help me fill in the gaps in whatever knowledge I have acquired till now.
A decision problem is a problem $X(D)$ that outputs for each input
instance $I$, a ...
1
vote
0answers
40 views
Variant of "Exact Cover by 3-Set "
Exact cover by 3-sets is 𝖭𝖯-complete:
Instance: Given a finite set $X = \{x_1, x_2, …, x_{3n}\}$ of $3n$ elements and a collection $C = \{(x_{i_1}, x_{i_2}, x_{i_3})\}$ of 3-elements subsets of $X$;
...
0
votes
1answer
33 views
Independent set problem with given black box
I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why.
Suppose that I'm given a polynomial ...
2
votes
0answers
79 views
Is it NP-hard to find different roots of different matrices simultaneously?
Consider the following problem:
input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$.
output: a ...
0
votes
0answers
28 views
Is Knapsack-optimization problem NP-hard while Knapsack-search problem NP-complete?
I am learning Computational Complexity.
Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that ...
0
votes
3answers
47 views
Are there any FNP-complete problems with a unique solution?
Are there any FNP-complete problems where there's only one possible solution?
For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest ...
0
votes
0answers
13 views
Need Help Solve an NP problem with an Approximation Algorithm
I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example.
Given $n$ objects, each with $k$ possible properties, ...
0
votes
1answer
35 views
Does reducing a NP Hard problem to a NP problem make that NP hard problem a NP Complete problem?
I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-...
2
votes
1answer
69 views
Find the class of the problem PP1 and PP2 using the information given below
Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
0
votes
2answers
39 views
Can you help me provide some examples of 3-co-SAT?
Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable， namely ...
1
vote
1answer
181 views
NP-completeness of satisfiability of formula over 50 variables
Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?
0
votes
0answers
17 views
Complexity class of computation of Homfly polynomial
It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
2
votes
1answer
58 views
Reduction from SAT to SAT with exactly k true variables
Let $L$ be defined as follows:
$\small L = \{(\phi, k) \mid \phi \in SAT \mbox{ and there is a satisfying assignment for $\phi$ having exactly $k$ true variables} \}$
I am struggling to show that $SAT\...
0
votes
1answer
38 views
If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?
Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$.
My question is, if $A\leq_P B$ and $B\in \...
-1
votes
1answer
39 views
K-Path-Problem is in $P$ or $NPC$
Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices?
How can we solve this problem? I think ...
2
votes
3answers
616 views
Are there problems in NP that do not reduce in polynomial time to any problem in NP?
As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?
1
vote
1answer
23 views
Consequences of a polytime algorithm for a decision problem reducible to 3SAT
If there is a polynomial time algorithm for a decision problem $A$, which is m-reducible to 3SAT, and 3SAT is NP-complete, does this prove that P=NP?
1
vote
0answers
36 views
Approximation classes for optimization problems with real values
Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.?
If my understanding is correct a ...
1
vote
1answer
55 views
How to convert Bipartite Perfect Matching to SAT?
SAT is $NP$-complete while Bipartite Perfect Matching is in NC under derandomization assumptions. How to convert Bipartite Perfect Matching from balanced bipartites to SAT without Cook-Levin?
0
votes
1answer
31 views
If problem A reduces to an NP-Complete problem B, can we say that A is in NP?
I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
I understand that the general way we show a problem A is in NP is to show there exists a poly-...
3
votes
1answer
119 views
Is 3-UNSAT problem coNP-complete?
The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is ...
0
votes
1answer
70 views
Tic-Tac-Toe in PSPACE
Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
-5
votes
1answer
67 views
Really confused
Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this?
P = NP
P ⊊ NP
P ≠ NP
NP ⊆ P
0
votes
1answer
35 views
How to prove that the generalized assignment problem (GAP) is NP-hard?
Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness?
The decision version of the generalized assignment problem is to determine ...
1
vote
1answer
66 views
What does an 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 P ...
0
votes
0answers
42 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 ...
-1
votes
1answer
79 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 ...
0
votes
2answers
104 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 ...
0
votes
1answer
42 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 ...
3
votes
1answer
110 views
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
38 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
33 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 \...
-2
votes
1answer
68 views
Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u} [duplicate]
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 $...
2
votes
2answers
162 views
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 ...
0
votes
1answer
74 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 ...
1
vote
1answer
76 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
241 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 ...
0
votes
3answers
59 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$. ...
1
vote
2answers
67 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
1answer
34 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
26 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 ...
2
votes
1answer
44 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 ...
0
votes
1answer
89 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
25 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&...
