Questions tagged [np]

In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
169 views

If NP=P, then does quantum mechanics have a classical interpretation? [closed]

Is it true that $BQP\subset NP$, if $NP=P$?
user avatar
  • 3,019
3 votes
1 answer
365 views

Root of polynomials in a finite field

I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number. For example : $p=2^{2020}-69$ ...
user avatar
  • 3,019
22 votes
2 answers
5k views

$\mathbf{P} = \mathbf{NP}$, what's the problem?

Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$. We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
user avatar
  • 3,019
2 votes
0 answers
85 views

Lower bound on the number of solutions of 2SAT

To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
user avatar
1 vote
1 answer
116 views

Boolean function : approximation by a linear function

Let $f$ be a balanced Boolean function. Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$ $g ...
user avatar
  • 3,019
8 votes
3 answers
921 views

Is there a website or a survey collecting all NP-complete problems on graph theory?

I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
user avatar
0 votes
0 answers
73 views

What does it mean to find an efficient algorithm for NP complete problems

Suppose I have a problem $P$, an instance $I$ and an algorithm $A$ that efficently solves $P$ for $I$. Let $P'$ be $P$ with additional constraints that are violated if $A$ is applied to $I$ and ...
user avatar
13 votes
3 answers
716 views

Undecidable infinite analogs of NP-complete problems?

In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...
2 votes
1 answer
77 views

$W[1]$-hard and FPT about the equitable tree-coloring problem

I am confused by the two conclusions in this paper (DOI link behind paywall at Springerlink). It shows that the equitable tree-coloring problem is $W[1]$-hard when parameterized by treewidth. However, ...
user avatar
0 votes
1 answer
80 views

Is minimum weight vertex cover problem NP-easy? [closed]

I think that Minimum weight vertex cover problem is NP-easy. However I don't know how to prove that. Does anyone know how to prove it?
user avatar
7 votes
1 answer
690 views

$\mathit{NP}$-hard statements which are $\mathit{NP}$-complete under the Riemann Hypothesis

$\newcommand\NP{\mathit{NP}}\newcommand\SAT{\mathit{SAT}}\newcommand\CH{\mathit{CH}}\newcommand\PSPACE{\mathit{PSPACE}}$Are there $\NP$-hard problems which are $\NP$-complete under the Riemann ...
user avatar
  • 12.8k
1 vote
0 answers
60 views

Subgraph isomorphism problem with linear map

I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem: Problem 1: Given two graphs $G=(V, E)$ ...
user avatar
  • 91
1 vote
0 answers
37 views

Computational complexity of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
user avatar
  • 71
1 vote
0 answers
91 views

Promise version of minimum distance

It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard. This immediately also says that given a code $C$, calculating minimum hamming ...
user avatar
  • 71
0 votes
0 answers
138 views

Computational practicality of proving a theorem by transforming into a map coloring and finding $P(3)$, where $P$ is the chromatic polynomial

So I have heard that you can transform a math statement into a map in such a way that proving the statement is true is equivalent to finding a $3$-coloring of that map. I'm also aware that you can ...
user avatar
  • 101
3 votes
1 answer
608 views

Is there an example of converting a mathematical statement into a three color mapping? [closed]

https://youtu.be/5ovdoxnfFVc?t=1118 At this point, prof Wigderson says it is easy to go from a mathematical statement to a graph coloring problem. The video does not provide an example of this, and a ...
user avatar
1 vote
0 answers
33 views

Finding valuable conjectures from NP-Complete problems [closed]

Let's suppose we've got an NP-Complete problem, such as the subset sum problem. There are conjectures that, if proven true, would place the subset sum problem to the P-Complete problem realm? If the ...
user avatar
-1 votes
3 answers
118 views

Are <sum, product, N> triplets unique and hard to solve? [closed]

This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so ...
user avatar
12 votes
1 answer
1k views

How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...
user avatar
  • 16.6k
2 votes
2 answers
145 views

Transforming an optimization problem to maxmin formulation

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...
user avatar
  • 491
2 votes
1 answer
166 views

What is the efficiency of this algorithm which decides the answer to the Boolean satisfiability problem? [closed]

I have just written a short javascript program which, given any boolean expression with $N$ variables, completes in N "ticks" of the clock and which makes the decision. I will explain this algorithm, ...
user avatar
3 votes
0 answers
121 views

Is the Weber problem a NP-hard problem?

The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...
user avatar
0 votes
1 answer
173 views

Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]

Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
user avatar
2 votes
0 answers
47 views

Proof for the NP-hardness of the Max-3-DCC Problem

The Max-3-DCC is the variant of vertex cycle cover problem where each of the vertex disjoint oriented cycles consists of at least 3 arcs and every vertex belongs to exactly one of those cycles; ...
user avatar
1 vote
0 answers
40 views

Determining the minimum weight maximal oriented subgraph of a complete directed graph

Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights. Questions: What is the ...
user avatar
1 vote
0 answers
117 views

Is bounded graph isomorphism $NP$ complete?

Fix a matrix $M\in(\mathbb Z\backslash\{0\})^{n\times n}$ where $\|M\|_\infty\leq 2^{poly(n)}$. Is the bounded graph isomorphism problem Given symmetric $A,B\in\{0,1\}^{n\times n}$ and $U,V>0$ ...
user avatar
  • 12.8k
14 votes
5 answers
1k views

Equivalent forms of the P vs. NP problem

Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral ...
user avatar
  • 1,942
2 votes
0 answers
69 views

NP - hardness of school scheduling problem with a restriction

I do have a real-life scheduling problem for a special education school. Basically, i have a binary variable containing teachers, subject, time slot and rooms as indices. The goal is to assign each ...
user avatar
  • 21
16 votes
2 answers
581 views

Is this kind of "Gerrymandering" NP-complete?

[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.] Consider the following simplified form of "Gerrymandering": You have $n^2$ ...
user avatar
1 vote
0 answers
58 views

Shortest Lattice Vector with restricted $x$

Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$. My questions ...
user avatar
  • 1,076
1 vote
0 answers
153 views

Is it known whether $\mathrm{NP \subseteq P/poly}$?

It is not immediately clear to me whether this statement is true or false. Can finite restrictions of NP problems be computed in polynomial time?
user avatar
3 votes
0 answers
49 views

Karp hardness of two cycles which lengths differ by one

Our problem is as follows: NEARLY-EQUAL-CYCLE-PAIR Input: An undirected graph $G(V,E)$ Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO Is it $NP$-...
user avatar
3 votes
0 answers
105 views

$\mathrm{NP}$-complete problems in graph theory: undirected vs. directed

Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)? Academic articles proving $\mathrm{NP}$-completeness of problems on ...
user avatar
1 vote
0 answers
86 views

descriptive complexity theory to attack computational complexity problems [closed]

What is the usefulness of descriptive complexity to attack computational complexity theory?what are the recent results in this direction? Thanks
user avatar
  • 11
1 vote
0 answers
73 views

Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
user avatar
12 votes
2 answers
407 views

Techniques for proving relaxed one-wayness of functions

Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...
user avatar
15 votes
3 answers
704 views

Representing mathematical statements as SAT instances

The following problem (call it THEOREMS) belongs to class NP. Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary. Output: "Yes" if ...
user avatar
  • 701
3 votes
2 answers
181 views

(How) do Better TSP Heuristics help in Answering the $NP=P$ Question?

This question is motivated by my impression, that finding better heuristics for the TSP problem (or any other $NP$-complete problem) is "only" of practical interest, but doesn't provide any progress ...
user avatar
16 votes
2 answers
553 views

NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
user avatar
  • 163
1 vote
0 answers
47 views

Cost associated set problem NP-hard

I have the following problem. I wonder whether or not it appears in the literature. Is it NP-hard? Given a set $S = \{1,2,\ldots,m\}$, and $A_1,\ldots, A_n$ are subsets of $S$. Each set $A_i$ has ...
user avatar
0 votes
1 answer
268 views

Finding a subgraph of cliques with the minimum total sum weight

Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...
user avatar
  • 103
3 votes
1 answer
273 views

Simple cake cutting puzzle

I got interested in a cake cutting problem from computational perspective. Suppose we have a piece of cake and we want to slice it into pieces using several cuts (straight lines). Each cut represents ...
user avatar
11 votes
3 answers
1k views

Is there a polynomial-time algorithm for untangling the unknot?

I've found assertions that recognising the unknot is NP (but not explicitly NP hard or NP complete). I've found hints that people are looking for untangling algorithms that run in polynomial time (...
user avatar
0 votes
1 answer
120 views

Continuous backpack with multiple choice items. NP prove

Continuous backpack with multiple choice items is the problem where you need to collect items by one from each of distinct sets and associate them with rational numbers so that their sum of weights ...
user avatar
  • 1
4 votes
1 answer
797 views

What arguments do exist against defining completeness in NP using injective Karp reductions?

It is crucial to use the right notion of reduction to define completeness inside NP. Different notions of completeness inside NP may have significant impact on the properties of complete languages. ...
user avatar
7 votes
3 answers
1k views

How slow are direct solutions of NP-complete problems on computers?

Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. ...
user avatar
  • 171
3 votes
1 answer
132 views

Covering a graph by trees with depth constraint

Given a graph $G$ and a depth constraint $h$, my question is: what is the complexity to find a tree cover of $G$, denoted as $T=\{T_1, T_2, ..., T_n\}$. For each $T_i$, its depth(height) is no larger ...
user avatar
  • 31
2 votes
1 answer
106 views

Minimum cover for sets in which each element appears in exactly 2 sets?

Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
user avatar
1 vote
0 answers
161 views

How I can prove the equality $P^{P_{\operatorname{space}}}=NP^{P_{\operatorname{space}}}=P_{\operatorname{space}}^{P_{\operatorname{space}}}$ [closed]

I know how to prove that if $A \in P^{P_{\operatorname{space}}}$ then $A \in NP^{P_{\operatorname{space}}}$ and $A \in P_{\operatorname{space}}^{P_{\operatorname{space}}}$. I don't know how to prove ...
user avatar
  • 19
2 votes
2 answers
412 views

How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT?

I am interested in the complexity of the following problem: GENERAL-SQUARE-PRODUCT INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a ...
user avatar