Questions tagged [np]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

Filter by
Sorted by
Tagged with
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?
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 ...
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-...
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 (...
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 ...
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 ...
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 ...
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 ...
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\...
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 ...
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 $...
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 ...
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 ...
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 ...
-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$?
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 ...
-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

1
2 3 4 5
14