Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
445
questions
0
votes
2answers
16 views
Decide whether an $n$-bit positive integer is composite
Question:
Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?
I know that for every composite number, a factor of the number is a ...
1
vote
1answer
14 views
Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?
The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial.
Why do we not study the ...
0
votes
0answers
39 views
Which is the most similar NP classic problem, if any exists, to this one?
Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
0
votes
0answers
21 views
NP problem solving
Prove that every NP problem is solvable in $O(2^{n^{k}})$ where $k$ is constant.
My approach was that, let's look at the 3-SAT problem. We can solve it by bruteforce in $O(2^n)$, where $n$ is ...
0
votes
0answers
42 views
Confusion about P versus NP [duplicate]
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
-2
votes
2answers
79 views
Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?
I claim to have solved the travelling salesman problem as follows.
(You will have to be familiar with djikstra's algorithm for this.)
1) I am about to start using djikstra's algorithm on any given ...
1
vote
2answers
55 views
P/NP - Polynomial Reduction vs Certificate
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.
How I understand polynomial reduction is that you can use it to ...
0
votes
2answers
49 views
An example of a computable problem that is not in P
I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set ...
1
vote
1answer
75 views
if $L \in NP$ then its mapping reducible to HALT?
This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?
1
vote
1answer
34 views
How can i prove that MAX-CUT is in NP?
How can i show/explain/prove that Max-Cut is in NP?
"For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as ...
5
votes
2answers
2k views
is FIND WORDS in P?
FIND WORDS is the following decision problem:
Given a list of words L and a Matrix M, are all words in L also in M?
The words in M can be written up to down, down to up, left to right, right to left,...
2
votes
1answer
61 views
If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?
According to this source,
If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...
2
votes
1answer
88 views
Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:
Suppose that a friend tells you that a given
graph G is hamiltonian, and then offers to prove it by giving ...
0
votes
0answers
43 views
Intersection of decision problems?
Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
8
votes
3answers
478 views
Simple interepretation problem regarding Polynomial Hierarchy?
So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for
$P^{NP}$
$NP^{NP}$
$coNP^...
1
vote
2answers
62 views
Is the certificate for primality testing polynomial in the length of the input?
If we were to assume that primality testing was in NP.
What would the certificate be, so that a polynomial time verifier can check the number X is indeed prime?
0
votes
1answer
55 views
Are there any “complete” languages in $coNP -NP$?
Suppose $coNP \neq NP$
language B would be called "complete" in $coNP-NP$ if:
$B\in coNP - NP$
$A\in coNP-NP \implies A\leq_pB$
Are there any "complete" languages in $coNP - NP$?
2
votes
1answer
43 views
D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$
Given that a language D has a polynomial verifier,
and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space.
How can I prove that $D\in P$ ?
My idea was to ...
12
votes
2answers
3k views
Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
2
votes
2answers
114 views
Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?
I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite ...
1
vote
1answer
44 views
Reducing 3 SAT to 3 SET PACKING
I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ...
3
votes
2answers
57 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
125 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
46 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
154 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
36 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
29 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
46 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
86 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 ...
3
votes
0answers
23 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 $...
6
votes
2answers
77 views
Sequence to explore the complexity of the NP problem
Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? ...
4
votes
0answers
75 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
34 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
65 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
90 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
39 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
174 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
111 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
29 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
32 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
43 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
427 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
218 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
194 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
37 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
45 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
299 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
88 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
48 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 ...
