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
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 ...