Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
665
questions
1
vote
1
answer
55
views
Turing Machines time complexity with regard to the NP and P problem
I'm studying Turing machines and I came across the following definitions:
NP is the set of problems that can be solved in polynomial time by a non-deterministic Turing machine.
and
Let t(n) be a ...
- 41
0
votes
0
answers
34
views
Why don't we consider that NP = co-NP while we can reduce Tautology problem into Satisfiability in polynomail time easily?
Let's determine if an expression is tautological or not and let's try this expression:
((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c).
We can turn this problem into CIRCUIT-SAT decision problem by asking if the ...
- 35
2
votes
0
answers
58
views
Exact Cover variant: partition a family of subsets into exact coverings
I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem:
Partition into $k$ Exact Covers
Input: A universe ...
- 111
0
votes
0
answers
41
views
Why does "NP is closed under Kleene star" proof reject correct word? [duplicate]
Show that P and NP are closed under Kleene star. I found possible solutions to these problems, more specifically:
P - finding all subwords from a giving word and looking if there is a connection ...
- 1
1
vote
1
answer
39
views
If every NP-hard language is PSPACE-hard then NP=PSPACE
To prove PSAPCE = NP we will show following inclusions :
NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then
SAT is also PSPACE-hard. Since every language in PSPACE can be
reduced ...
- 173
0
votes
2
answers
38
views
Are all np-complete problems also np-hard?
Are all np-complete problems also np-hard?
In other words, is np-complete a subset of np-hard?
I don't think it is entirely clear from the illsutration below, so I just wanted to quickly ask to ask to ...
0
votes
1
answer
17
views
How to prove that a subset of a language L is related to NP while L is related to P?
a friend sent me a question where we're given language $L$ and its subset $E(L)$ such that:
$$E(L)=\{E(w)\ |\ w\in L\}\\\text{such that}\\
E(w)=\{w_{even}=\sigma_2\sigma_4\dots\ |\ w=\sigma_1\sigma_2\...
- 456
9
votes
1
answer
2k
views
Why rectangle packing is NP-hard but maybe not in NP?
Recently I studied a MIT open course.
In lecture2, it is stated that Rectangle Packing is NP-hard.
I can understand this because the problem can be reduced to 3-partition problem
But I don't know why ...
- 153
0
votes
1
answer
40
views
Reducing to an NP-complete problem
If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?
I think we should be able to say that $R$ is in NP since an instance of $...
1
vote
1
answer
56
views
Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?
I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2.
Set cover problem with sets of size 2
The ...
-1
votes
1
answer
34
views
What kind of problems in the world can be classified into PSPACE categories?
For instance can we categorize the following problems into NP-Hard ?
Is the Universe finite ?
Is there life after death ?
What came first, the chicken or the egg ?
My question is more around what ...
- 99
3
votes
1
answer
102
views
4-SAT but two literals per clause must be true
I'm trying to show that a modified 4-SAT in which at least two literals per clause must be true is NP-complete. I'll call it $4_2$-SAT. I understand the reduction from 3-SAT to 4-SAT, and I know why $...
- 31
0
votes
0
answers
12
views
Np polynomial reduction
There is a theorem that states if $(B∈NP)$ and $(A\propto B)$, then $(A∈NP)$, then what if ($A∈NP$) and $(A\propto B)$, does it means that $(B∈NP)$?
($\propto$ being a polynomial many-one reduction)
- 1
0
votes
1
answer
139
views
If A reduces to B and B reduces to C, does that mean A reduces to C?
If A is in the class P, B is NP-complete, and C is not in the class NP. And A reduces to B and B reduces to C.
Which statements are true?
A is in the class NP.
A reduces to C.
If S is a candidate ...
- 103
1
vote
1
answer
47
views
How can EXP^P be characterized?
I had a question about EXP^P (EXPTIME with access to a P oracle). I thought I had read somewhere that EXP = EXP^P, and that seemed fairly intuitive to me: I thought "adding polynomial power to ...
0
votes
2
answers
38
views
Suppose we know for certain that P = NP. Can we say that NP = co-NP?
i tried to see from my course book at university but i didn't understand much, can someone help me? even looking around on the internet I did not find anything useful
- 1
1
vote
1
answer
47
views
Is "deterministic non polynomial time" the same as "non deterministic polynomial time"? [duplicate]
I have always though that NP consists of problems solved in a non polynomial time by a deterministic Turing machine. Recently I discovered that NP classifies all the problems solved by a non ...
- 11
-2
votes
1
answer
38
views
Deciding whether there always exist k different disjoint paths between any pair of vertices in a graph
Given a graph $G$ and an integer $k$, is it NP-complete to decide whether there always exist $k$ different disjoint paths between any pair of vertices of $G$?
- 1
0
votes
1
answer
43
views
Is SUBSET SUM only for positive integers in P or NP?
Since UNARY SUBSET SUM is in P, and a positive-only SUBSET SUM problem could be represented in unary, I struggle to see why it wouldn't be the case that it is in P, when restricted to positive numbers?...
1
vote
1
answer
73
views
Why NP-Complete reduction is not reversible?
I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms ...
- 65
2
votes
1
answer
21
views
How we transform IS inputs to VC (reduction)?
I would like to clarify something in my understanding of proving a problem to be NP-hard.
So in short, what I know is that:
"If I have a problem A that I want to prove that is NP-hard and another ...
- 201
-1
votes
1
answer
80
views
if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
I don't know how to solve this.
Show that if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
- 7
1
vote
1
answer
70
views
Why is SET PACKING in NP?
I have seen an lot of proves why SET PACKING is NP complete. However, in every prove it states that SET PACKING is clearly in NP. It might be a stupid question, but is not so clear to me. I see that ...
- 13
2
votes
3
answers
104
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 ...
- 21
5
votes
1
answer
510
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 ...
- 683
0
votes
2
answers
91
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 ...
- 1
6
votes
1
answer
441
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$, ...
- 63
1
vote
1
answer
38
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-...
- 11
3
votes
1
answer
225
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 ...
- 31
0
votes
0
answers
22
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 ...
- 5
1
vote
0
answers
58
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$;
...
- 11
0
votes
1
answer
61
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 ...
- 5
2
votes
0
answers
81
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 ...
- 21
0
votes
0
answers
74
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 ...
- 101
0
votes
3
answers
53
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 ...
- 101
0
votes
0
answers
17
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, ...
- 101
0
votes
1
answer
36
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-...
- 23
2
votes
1
answer
86
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 ...
- 23
1
vote
2
answers
73
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 ...
- 153
1
vote
1
answer
185
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?
- 113
2
votes
1
answer
101
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
1
answer
60
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 \...
- 103
-1
votes
1
answer
56
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 ...
- 123
2
votes
3
answers
697
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}$?
- 31
1
vote
1
answer
27
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?
- 115
1
vote
0
answers
38
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 ...
- 41
1
vote
1
answer
119
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?
- 2,824
0
votes
1
answer
52
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-...
- 159
4
votes
1
answer
206
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 ...
- 145
0
votes
1
answer
92
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?
- 19