# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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 ...
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 vote
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 ...
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 ...
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\...
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 ...
40 views

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)
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 ...
1 vote
47 views

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 vote
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 ...
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$?
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
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 ...
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 ...
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 = Σ*
1 vote
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 ...
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 ...
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 ...
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 ...
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$, ...
1 vote
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-...
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 ...
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 ...
1 vote
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$; ...
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 ...
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 ...
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 ...
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 ...
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, ...
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-...
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 ...
1 vote
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 ...
1 vote
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?
101 views

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 ...
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}$?
1 vote
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?
1 vote
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 ...
1 vote
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?
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-...