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
1 answer
10 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
35 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
51 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
69 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
16 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
29 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
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
  • 15k
1 vote
1 answer
31 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
43 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,632
1 vote
0 answers
40 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,632
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
253 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
38 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
58 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
52 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
  • 83
0 votes
1 answer
87 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
51 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, ...
Jul Wac's user avatar
  • 191
0 votes
0 answers
93 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
40 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
168 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
42 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
50 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
169 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
99 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
68 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
0 votes
0 answers
21 views

reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
user's user avatar
  • 1
1 vote
1 answer
48 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
197 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
86 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
110 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
27 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
0 votes
0 answers
70 views

Finding a Polynomial Time algorithm for the 3-SAT Problem

Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause : Ai = (xr $\lor$ xs $\lor$ xt) where 1 $\le$ r,s,t $\le$n and ...
Pathlessbark8's user avatar
0 votes
0 answers
21 views

Construct polynomial-time algorithm to decide whether there is a linear classifier containing all points in X and no points in Y [duplicate]

Consider n-dimensional linear classifiers, that is, subsets of R n that have the form {(x1, x2, . . . , xn)| a1x1 + a2x2 + · · · + anxn ≥ b} for some real numbers a1, . . . , an and b. Given as input ...
AZ689's user avatar
  • 1
0 votes
0 answers
18 views

Analogue of NP for oracle problems

I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems. The ...
Andrew Baker's user avatar
0 votes
1 answer
86 views

Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier

For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X a1x1 + a2x2 + ... + ...
automatically's user avatar
0 votes
0 answers
37 views

Is PrefixFreeNP=P?

I was given the following definition of a verifier: Verifier $V$ is called $PrefixFree$ if for every $x,y$ such that $V(x,y)=1$, then for every $y'$ (which is not an empty string, $y'\ne\epsilon$) $V(...
MiddleEasternPrince's user avatar
4 votes
2 answers
111 views

Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)

Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true? $A \leq_m$ B $B \leq_m$ A In other words, is there always a relationship between any two arbitrary NP-hard ...
Andrew Baker's user avatar
0 votes
0 answers
21 views

$NP\subseteq P/poly\implies PH\subseteq P/poly$

We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
Soham Chatterjee's user avatar
1 vote
1 answer
52 views

Do all P problems reduce to all NPI problems?

It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in ...
Andrew Baker's user avatar
0 votes
1 answer
42 views

Do reductions (in NP and other classes) follow a linear path?

NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness. There are other problems in NP that are also "equal" to one ...
Loic Stoic's user avatar
2 votes
3 answers
154 views

Are there problems in NP that would solve P vs NP, but are not NP complete

NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is if we were to find some ...
Loic Stoic's user avatar
0 votes
1 answer
99 views

Time complexity to convert a truth table to a boolean circuit

The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table? But how about going the ...
Loic Stoic's user avatar
1 vote
1 answer
32 views

I would like to know what are the directions to work on if I want to prove that $NP=coNP$?

I am currently learning about NP and coNP related content and have been exposed to the$NP \overset{\text{?}}{=}coNP$ problem. I would like to know what are the directions to work on if I want to prove ...
lz9866's user avatar
  • 315

1
2 3 4 5
16