Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np]

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

3
votes
2answers
47 views

Proving a problem as NP-complete

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs ...
0
votes
1answer
85 views

Proving NP completeness of maximal length path

I have this question to answer: For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
3
votes
1answer
32 views

Quantum vs classic in NP-hard problems

Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
3
votes
2answers
74 views

Why isn't the Generalized Super Mario Bros. obviously in NP?

It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) ...
1
vote
1answer
23 views

Reduction from NP-complete problem to unknown complexity problem and vice-versa

Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity. Question: If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required ...
2
votes
0answers
22 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
3
votes
1answer
39 views

Pebble game lower bound?

This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433. Why is it not considered proof of constructive example for a function in ...
3
votes
1answer
82 views

NP-completeness of Induced disjoint paths

In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs. Our problem ...
2
votes
0answers
19 views

$NP$, $P^{TFNP}$ and $P^{UP}$

Is it possible $NP\subseteq P^{TFNP}$ holds or $NP\subseteq P^{UP}$ holds without the polynomial hierarchy collapsing? Is there problems in one of each of the classes from $NP$, $P^{UP}$ and $...
4
votes
0answers
72 views

Matrix covering by squares

I wonder about the following decision problem : Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$. Question: is it possible to cover all the ones of the ...
0
votes
1answer
21 views

Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from ...
0
votes
1answer
63 views

If an algorithm solves an NP problem, for what f(n) can we claim that R belongs to TIME(f(n))?

Let $R$ be some problem in NP. Suppose algorithm of solution check M(x,y) runs in time $O(n^3)$ and uses $y$ additional information, s.t $y \leq 5 \log n$ bits. For what $f(n)$ can we claim that $R$ ...
7
votes
1answer
1k views

Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this : https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg I wonder if ...
4
votes
0answers
88 views

Maximum coloring of a graph with paths through uncolored vertices

Last night, I had a dream involving an intelligent spider which was only able to communicate by crawling around on a grid of words/phrases, like this one: When I woke up, I wondered why some of the ...
2
votes
1answer
29 views

Shortest hamiltonian path for different dimension points

The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$. For example if for $k=1$, the shortest Hamiltonian path will be the sorted ...
0
votes
1answer
163 views

NP hardness of unique Puzzle Generation

Introduction For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The ...
1
vote
1answer
82 views

P vs NP question from GeeksforGeeks

From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/ Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to ...
3
votes
0answers
28 views

Reachability games with banned vertex repetition

I have bumped into this problem while working on something model checking related and can't seem to find materials or efficient solutions for it. I couldn't even find a name for it. We have a ...
-1
votes
1answer
25 views

3-Coloring Graph problem

Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is NP instead of NP-complete? $$\mathrm{3COLOR} = \{\langle G \rangle \mid G \text{ is colorable with 3 ...
1
vote
0answers
28 views

How to reduce independent set to longest path

A friend and I have tried for several hours to try and find a reduction from independent set to longest path, but the results have not been fruitful. We have tried many methods of graphing and ...
4
votes
2answers
336 views

Why was primality test thought to be NP? [duplicate]

To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $\sqrt{n}$, meaning that the complexity would be $O(\sqrt{n})$. In my opinion, $O(\sqrt{n}) < O(n)$ so this simple ...
1
vote
1answer
193 views

for two languages in $NP$ does one of them karp reducible to another?

$\forall A, B \in NP \implies A<_m^{poly}B. \lor B<_m^{poly} A.$ I want to know is there any work around this theorem? or is it correct?
0
votes
1answer
93 views

Complement of NP-complete can be in NP

Here are a couple of questions I struggle with. (We use $A'$ to denote the complement of the problem $A$.) A problem $A$ is NP-complete if and only if $A'$ is in NP? A class problem $A$ is NP-...
0
votes
1answer
33 views

Can a NP problem be reduced to another NP problem?

I have three related questions which have been bothering me for a while now... Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I ...
1
vote
1answer
43 views

Is this problem in NP?

I am new in complexity theory and have a doubt. If you have a language (alphabet) L (for example {"a";"b";"Y","0","1","◄"}) and a Dictionary D (for example {"abY";"Ú■";"ba";"000001◄";"FFG","342"}) ...
1
vote
2answers
268 views

Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?

I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class: \begin{align} C=\left\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are ...
1
vote
1answer
77 views

A tricky P=NP problem

Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under ...
0
votes
0answers
46 views

P Langauage to NP Reduction in Polynomial Time [duplicate]

Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings. I tried ...
0
votes
0answers
25 views

Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate]

Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?
2
votes
1answer
154 views

Reduction to a vertex cover problem-like with weighted vertices and edges

Description Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas: $G$ is an undirected graph $K \le |V|$ $L > 0$ is the maximum limit Each vertex $v \in V$ has a weight $...
0
votes
0answers
12 views

Proving k-partition problem is NP [duplicate]

For any integer k ≥ 2, the k-Partition problem is said to be a sequence of positive integers (w1, w2, . . . , wn), is it possible to partition them into k groups having equal sums? I'm confused on ...
1
vote
2answers
112 views

Can someone explain why the MAX-CUT problem is in NP?

Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset? I'm ...
2
votes
1answer
39 views

Dominating set of given size $k$ in $O(2^k |V| |E|)$

Recently I've encountered an interesting case of dominating set problem: given an unweighted and undirected graph $G(V, E)$ and knowing that it contains a dominating set of size $k$, find any such ...
1
vote
1answer
41 views

Does a polynomial solution to weakly-NP Complete problem mean P = NP?

Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.
3
votes
1answer
58 views

If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?

If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens? Does it imply $NP\neq EXP$? Is there any other consequences such as $BPP\neq EXP$? Does it also give $PSPACE\subseteq DTIME[n^{O(\log n)}]$?
2
votes
1answer
286 views

Reducing 3SAT to a Set Splitting Problem

I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the ...
1
vote
1answer
23 views

Show: “Checking no solution for system of linear equations with integer variables and coefficients” $\in \mathbf{NP}$

I've been struggling for a while trying to solve this problem: Show that the following problem is in $\mathbf{NP}$: Check that a system of linear equations with $m$ integer variables and integer ...
2
votes
2answers
228 views

Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
0
votes
1answer
103 views

Showing party invitation problem is np-complete

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
1
vote
1answer
57 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
1answer
37 views

Finding a suitable NP-complete problem for reduction

We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a ...
1
vote
1answer
94 views

Is this partitioning problem NP-complete?

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
1
vote
1answer
44 views

How to show that this decision problem is in co-NP?

Given a set of strictly positive numbers $a_1, ..., a_n$, the problem is to determine if $\lfloor n/2 \rfloor$ different indexes $i_1, ..., i_{\lfloor n/2 \rfloor}$ exist so that $$\frac{a_{i_j}}{a_{...
0
votes
1answer
45 views

Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]

Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how ...
2
votes
0answers
20 views

Reducible from vertex cover for only some inputs

Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\...
0
votes
0answers
36 views

Why finding out an independent set of size k is in NP-C and not in P? [duplicate]

I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P. P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is ...
3
votes
1answer
46 views

Proving NP hardness about graph creation problem with triangle number

I have graph creation problem. Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
2
votes
0answers
26 views

Karp hardness of two vertex sets in a digraph

Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that: $|S|+|T|=k$ For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
1
vote
2answers
36 views

Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$. Is this a new result? If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?
1
vote
0answers
28 views

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?