Skip to main content

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
1 vote
0 answers
34 views

Graph with an exponential number of paths

I am looking at the language $F$ containing all $G,v_0,v_1$ s.t.: $G$ is undirected $G=(V,E)$ $v_0,v_1\in V$ $|V|=n$ There are $2^n$ paths between $v_0$ and $v_1$ I would like to prove that $F\notin ...
Benicio Agüero's user avatar
1 vote
1 answer
100 views

Polynomial solutions, one less

Let $L$ be a language in the class $FP$ of all polynomial-time solvable problems. The class $FP$ is defined by having a TM $M$ s.t. for any $x$ it computes in polynomial time a $y$ s.t. $(x,y)\in L$. ...
Dan D-man's user avatar
  • 524
-1 votes
1 answer
28 views

Acceptance of Turing Machines is NP-Hard?

I had a question in my exam 'Show that the acceptance of turing machines is NP-Hard'. How do I go about this question?
josh hackentoff's user avatar
0 votes
0 answers
35 views

Equivalent definition of a PTNDTM?

$NP$ is the class of problems with a polynomial time non-deterministic turing machine which can determine whether an input is in a certain language or not. It can be seen as polynomial time ...
Benicio Agüero's user avatar
1 vote
0 answers
20 views

$\mathsf{NP}$ vs. $\mathsf{coNP}$ and sparse sets

Consider the following statement: If there exists a sparse set of negative (the ones whose answer is no) instances $I$ such that for every negative instance $a$ ...
rus9384's user avatar
  • 1,684
0 votes
0 answers
20 views

PCP is undecidable, but seems also NP [duplicate]

I've seen the proof that the Post Correspondence Problem is undecidable -- let's call this the problem of taking a finite collection of tiles with top and bottom labeled by any two strings, and ...
Addem's user avatar
  • 367
1 vote
0 answers
30 views

NP-hardness of subset sum of multiple supersets

Given the following problem: Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$ Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{...
SimonNW's user avatar
  • 161
0 votes
1 answer
33 views

A decision procedure for PCP

I have read that the Post Correspondence Problem is undecidable. Let's say this is the problem of having a finite set of "dominoes" with a string in the top and another string on the bottom....
Addem's user avatar
  • 367
0 votes
1 answer
38 views

Show that $PLANAR \in co-NP \cap NP$

The fact that the language of planar graphs is in $co-NP$ is easy to show because the complexity of finding a Kuratowski subgraph is $O(|V|)$. But what about $NP$? Any help is appreciated.
Dave the Sid's user avatar
-2 votes
1 answer
27 views

How do you show that Cosmic Kite Problem is NP complete?

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
Nicolò Bonacorsi's user avatar
0 votes
1 answer
48 views

NP-Hard version of TSP if P=NP

If P=NP (polynomial time algorithm for determining whether there exists a route smaller than L) would the NP-Hard version of TSP (finding the minimum distance route) still be NP-Hard? We would only ...
David's user avatar
  • 3
3 votes
1 answer
70 views

Does $A^B = A^C$ imply $B = C$?

I am familiar with the Baker, Solovay, Gill result of non-relativization of P vs NP problem. They showed that $\exists A \text{ s.t }P^A \neq NP^A$. But since we are referring to $P, NP$ as models of ...
Zee's user avatar
  • 243
1 vote
1 answer
23 views

Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?

I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
Wisdom Iwueze's user avatar
1 vote
1 answer
127 views

Prove "Vertex Cover OR Clique" is NP complete

Instance: An undirected graph $G$ and a positive integer $k$ Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$? Obviously, this problem is solved by polynomial ...
Hugh Mann's user avatar
1 vote
1 answer
40 views

$L_1\in P$ , $L_2\in NP$, is it possible that $L_1\cup L_2 \in P$

Prove\Disprove\Prove that equivalent to $NP=P$ or $NP\ne P$ given $L_1 \in P$ , $L_2 \in NP$ is $L_1 \cup L_2 \in P$? Obviously $L_1 \cup L_2 \in NP$ because NP is closed under union and $P \subseteq ...
Neta R's user avatar
  • 13
1 vote
1 answer
53 views

Proof that nondeterministic TM runs in exponential time

Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. ...
wytubev's user avatar
  • 13
0 votes
1 answer
19 views

Two transition functions def of NP

I've seen a definition of NP alluded to in different texts where at each step an NDTM makes a nondeterministic choice between two transition functions and behaves accordingly. It seems like even in a ...
user167426's user avatar
1 vote
0 answers
40 views

How could it be the case that NP != EXP? Do we know of any problems in EXP that are not in NP? [duplicate]

I know that NP is a subset of EXP, but I cannot find any resources talking about whether NP = EXP or not. My intuition tells me that any problem that requires exponential time to be solved with a DTM ...
Aland Ameer's user avatar
4 votes
0 answers
71 views

Extending Fagin's Theorem to the Polynomial Hierarchy

Fagin's Theorem (see Wikipedia and these lecture notes) states that there is an equivalence between second-order logic (SOL) formulas with existential quantifiers, and problems in NP. I was wondering ...
UserA2000's user avatar
0 votes
0 answers
23 views

Proof Closer String/Consensus String/Center String is NP-hard

Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
shinichi's user avatar
2 votes
0 answers
31 views

How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it. Fur- thermore, if a polynomial worst-case time ...
An5Drama's user avatar
  • 203
16 votes
4 answers
3k views

Why is Integer Linear Programming in NP?

The decision version of the problem Integar Linear Programming is the following: Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$. Question: is there a ...
Nathaniel's user avatar
  • 15.8k
1 vote
1 answer
69 views

Subset ${\tt XOR}$ problem

Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation. Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
Dominic van der Zypen's user avatar
1 vote
1 answer
44 views

Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?

The following problem has made me ask this question: Given a boolean formula $\varphi(X)$ decide if there exists a quantification of $\varphi(X)$ with $k$ $\forall$ quantifiers that holds true. ...
rus9384's user avatar
  • 1,684
1 vote
0 answers
43 views

Is $\mathsf P$ low for every complexity class between itself and $\mathsf{NP}$?

We know that $\mathsf P$ is low for itself. It's also low for $\mathsf{NP}$, $\mathsf{RP}$, $\mathsf{UP}$ and some other complexity classes that contain $\mathsf P$ and are contained in $\mathsf{NP}$. ...
rus9384's user avatar
  • 1,684
0 votes
0 answers
25 views

Computational Learning Problem: 3-DNF Reduction

I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R d and Y = {0, 1}. Consider the class of Binary classifiers given by intersection of ...
Mr.Zhang's user avatar
-3 votes
1 answer
277 views

If Q* can break encryption would that prove P=NP?

At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
Asleepace's user avatar
0 votes
1 answer
42 views

Pseudopolynomials and $NP$ problems like $CLIQUE$

Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be ...
CuriosityScream's user avatar
0 votes
1 answer
30 views

Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?

$f$ and $g$ being known functions. We suppose that the problem is solvable. To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
someone's user avatar
  • 11
2 votes
1 answer
62 views

Subset sum reducible to barter economy problem?

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
redbull_nowings's user avatar
0 votes
1 answer
63 views

Is the class NP closed under complement? (Follow-up)

As a follow up to this question already been asked here, I was wondering - if we supposed that P != NP, would then the following reasoning be correct: In NP problems we can only verify in poly-time ...
Meki21's user avatar
  • 93
0 votes
1 answer
121 views

Constructing an SAT formula from a Clique graph

We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand. From my knowledge when ...
emily-cs's user avatar
1 vote
1 answer
71 views

Why is infeasibility of linear programming considered to be an NP problem?

I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
Namrata Banerji's user avatar
19 votes
2 answers
4k views

Why are computability problems always written in full caps?

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
Rexon112's user avatar
  • 191
0 votes
0 answers
94 views

Is NP=RP(2^-n)?

I believe its true but struggle to prove. I know NP=union over positive c's of RP(2^-(n^c)) and from here to prove that RP(1/2^n) contained in NP is immediate. the other side is the problem. I've ...
Tomer Thaler's user avatar
0 votes
1 answer
33 views

If I want to prove that a problem is in NP, can the vertifier use exponential space?

I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate ...
user606273's user avatar
0 votes
0 answers
42 views

Investigating the Claim: co-$NP\subseteq NP\text{/}P$ implies $\Sigma_3^P=\Pi_3^P$ and Collapse of the Polynomial Hierarchy?

I have been studying the polynomial hierarchy recently, and I came across an intriguing claim that I would like to explore further: Assuming co-$NP\subseteq NP\text{/}P$, the claim states that it ...
Straw User's user avatar
1 vote
1 answer
173 views

What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
Flowy Poosh's user avatar
0 votes
0 answers
48 views

SMALL-FACTOR is not NPC. Is the statement true or false?

Given the SMALL FACTOR problem where: INPUT: an integer N and an integer k OUTPUT: yes ⇐⇒ N has a prime factor ≤ k. I know that SMALL-FACTOR problem ∈ in NP ∩ CO-NP. If it were NP-Complete we would ...
user161646's user avatar
1 vote
1 answer
51 views

What are the necessary requirements for proving NP is closed under complement?

I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why. $VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
Skynet's user avatar
  • 53
0 votes
0 answers
68 views

if it were shown that every algorithm that solves SAT must have complexity Ω(n^(log n)) then P≠NP?

Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong? I can't find a formal proof
PatrickBateman's user avatar
1 vote
0 answers
179 views

if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)

$L^\complement$ = the complement of L is it true that if $L\in NPComplete $ and $L\leq_p L^\complement \rightarrow P=NP$ basically asking if the following statements are correct $if (L\in NPComplete ) ...
Skynet's user avatar
  • 53
2 votes
1 answer
115 views

How to provide a reduction from 3SAT to domatic number problem

How to provide a reduction from 3SAT to domatic number problem. Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, ...
Hughson's user avatar
  • 21
1 vote
1 answer
81 views

Hardness of the k-center problem with relaxed triangle inequality

Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle ...
TheCollegeStudent's user avatar
25 votes
13 answers
6k views

False proofs that look correct

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
proof-of-correctness's user avatar
1 vote
1 answer
53 views

P NP R RE closures

I wrote the following table for all the closures in those classes. is anything there incorrect? also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
Skynet's user avatar
  • 53
1 vote
1 answer
255 views

is the class NP closed under set difference?

I know P is closed under all Boolean operations, but what about NP? is NP closed under set difference and symmetric difference? is this table accurate? Edit: updated table:
Skynet's user avatar
  • 53
0 votes
2 answers
89 views

Can all NP-complete problems be reduced to NP?

I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around? Can all NP-Complete be reduced to NP problems? My understanding is ...
Joan Marcual's user avatar
0 votes
3 answers
114 views

If X is poly-time reducible to Y and X is in P, then Y is in P

The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
Uzair Siddiqui's user avatar
1 vote
0 answers
28 views

Class of optimization problems whose decision versions are in P

NPO is defined to be the class of optimization problems whose decision versions are in NP. I would like to get the complexity class of optimization problems whose decision versions are in P. Is such ...
Samuel Bismuth's user avatar

1
2 3 4 5
16