Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
689
questions
0
votes
0
answers
11
views
Subgraph Isomorphism Problem NP complete?
I found many solution online on how to reduce Subgraph Isomorphism problem to Clique, but how do I prove that it is NP complete by reduction from independent set?
I'm struggling to figure out this ...
-2
votes
1
answer
28
views
How to prove that this is NP complete
I have the following problem: Given an undirected graph with n vertices v1,…,vn, a positive integer weight on each edge, and a n×n symmetric matrix Rij. The objective is to find a subset S of the ...
-1
votes
1
answer
31
views
Showing NP-completeness of a graph problem with vertex capacities
The problem:
Given an undirected graph G = {V, E}, a source-vertex s, and each vertex having a "capacity" between 0 and |V|, is there a tree which covers all vertices and does not extend ...
2
votes
2
answers
61
views
Why does showing that a NP problem is not NP-complete implies P$\neq$NP?
I found in this answer that if a problem is shown to be NP but not NP-complete then P$\neq$NP. What is the argument to prove this statement?
- 36
0
votes
1
answer
29
views
Showing NP-Completeness
I just newly started looking into computational complexity.
Since we don’t know if P = NP, we would like to have a way of saying “This problem is in NP and is really hard unless P = NP.”
This is made ...
- 23
1
vote
1
answer
29
views
Reducing problems to solve easier problems
Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$?
I've been learning about NP-Hardness recently and seems that the answer is no. Whenever ...
- 13
0
votes
1
answer
42
views
How to prove that this problem is NP Complete
I have a problem set about NP Completeness proofs and I'm struggling to approach this problem:
An organizer would like to arrange all the participants in a
circle where neighboring two students must ...
1
vote
1
answer
272
views
NP-Complete Reduction
Prove the following problem is NP-Complete:
The problem gave a directed graph G, and several subsets of vertices of such graph are being specified as T1,T2,....Tn, and the subsects could intersect, ...
- 13
-3
votes
1
answer
31
views
Given a list of numbers L and a target k, is there a subset of numbers from L whose product is k?
Is there any dynamic way of solving this problem? I would thank any help, I know the Subset sum Problem, but for solving it dynamically u have to create a matrix but here is not posible as the colums ...
1
vote
1
answer
26
views
In NP-hardness, can any category reduce to itself? How can you intuitively explain which categories reduce to the others?
I'm trying to understand how problems in NP-hardness reduce to one another. As I understand it now, if X reduces to Y, Y is at least as hard as X.
What I think that means, and would like confirmed or ...
- 11
0
votes
1
answer
57
views
Does a language have the same time complexity as its complement language?
If $L ⊆ \{0, 1\}^*$ is a language, then we denote by $ \overline{L}$ the complement of $L$
For example, the definition of $coNP$ is $coNP =\{L | \overline{L} \in NP\}$
The complement of $SAT$ language ...
- 163
0
votes
1
answer
46
views
Traveling salesman problem on an incomplete graph
In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the ...
- 333
1
vote
1
answer
47
views
What is the complexity of problems with randomized polynomial time verification?
Imagine a Problem $A$ with input size $n$ for which you can get a proof certificate (polynomial number of bits).
Next you try to use this string to verify if your problem is solved or not.
You know ...
1
vote
0
answers
32
views
A NP-complete problem with difficult NP membership proof
A proof of $\mathsf{NP}$-completeness for a decision problem requires two things:
$\mathsf{NP}$ membership;
$\mathsf{NP}$-hardness.
It is often the case that the $\mathsf{NP}$-hardness part is the ...
- 9,664
0
votes
1
answer
78
views
Does the halting problem belong to NP class of problems?
On the one hand it does not belong to NP problems because it simply is not solvable and is undecidable and on the other hand it is an NP problem because there are claims that it is NP-hard and ...
- 1
2
votes
1
answer
65
views
Is there an algorithm for this decision problem that is better than brute-force?
Apologies for the vague title. This decision problem has applications to graph coloring but I have not found a name for it in the literature.
I am trying to improve my algorithm for a decision problem....
0
votes
1
answer
31
views
Examples of problems in NP but not in P which we haven't proved NP complete
If we find a problem we know for sure is in NP but not in NP-complete or P, we'll have proved P!=NP. One approach then is to identify problems in NP (but not P) we haven't been able to show to be NP-...
- 333
0
votes
1
answer
28
views
Construct an objective function that favors the sorted permutation
I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (...
- 333
0
votes
1
answer
30
views
Node weighted Steiner Tree Problem where all Nodes have the same Weight
The node weighted Steiner Tree Problem as found in this compendium:
$\textbf{Instance}: \text{Graph } G = (V, E)\text{, set of terminals } S \subseteq V \text{ and a node weight function } w:V \to \...
- 103
0
votes
0
answers
72
views
Reduce the independent set problem to the set packing problem
I got this question in my compsci homework and tried the reduction from the solution with an example and it doesn't seem to want to work.
Here's the proposed reduction:
The independent set problem ...
1
vote
1
answer
36
views
Is there a hypothesized "complete" class of problems between P and NP-hard?
For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are
between
complete
By between, I mean ...
- 483
2
votes
2
answers
136
views
How can we show that P is not closed under taking all long prefixes?
Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language ...
- 279
2
votes
0
answers
29
views
Reductions from 3-SAT that won't work directly from SAT
Our prof talked about why it's good to know that 3-SAT is NP-complete because it's easier to craft reductions from it than from plain SAT.
However, all the examples we've seen (reduction to ...
- 21
0
votes
0
answers
34
views
To what complexity class does this language belongs?
I am currently trying to learn some more about complexity classes. I found this exercise but I cannot find a proper solution to this exercise:
I know this is in NP, can I also say it is in P? If that'...
0
votes
2
answers
56
views
Problem in $NP \cap coNP$ and in P implies $NP=P$?
Suppose that we have a problem in $NP \cap coNP$, if we find an algorithm that solves the problem in P, does this mean that $NP=P$?
- 401
0
votes
1
answer
40
views
Given the current knowledge about complexity class, what can we say?
I am a CS student. I am looking at some questions my professor made and I got stuck in this one.
"Which one of the following inclusions between complexity classes is coherent with the current ...
1
vote
1
answer
70
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
39
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
75
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
43
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
188
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
47
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
19
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\...
- 454
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 ...
- 165
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
87
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
35
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
261
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
13
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
266
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
55
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 ...
- 143
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
76
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
45
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
82
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
79
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
23
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 ...
- 211
-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
123
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
115
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