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?
