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

98 questions
Filter by
Sorted by
Tagged with
136 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 ...
142 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, ...
71 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 ...
62 views

### A variant of weighted set cover problem

I came across a paper that proves a generalized version of the weighted set cover problem is NP-complete. The problem is stated as follows: Given a collection of $n$ elements, a collection of ...
39 views

### Effect of uniqueness of optimal solution on difficulty of np-hard optimization problems

Question: is it harder to find an optimal solution of an NP-hard optimization problem by exact deterministic algorithms if the optimal solution isn't unique or do multiple optimal solutions lead to ...
145 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 ...
43 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; ...
34 views

### Transformation of asymmetric traveling salesman problems into Chinese postman problems

I have found transformations of Chinese Postman Problems (CPPs) into Asymmetric Traveling Salesman Problems (ATSPs), but didn't find anything about transformations in the opposite direction. Having ...
34 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 ...
111 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$ ...
843 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 ...
58 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 ...
260 views

### Is this kind of “Gerrymandering” NP-complete?

[I posted this on math.stackexchange.com 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$ squares ...
48 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 ...
114 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?
46 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 ...
102 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 ...
68 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
69 views

426 views

### Is finding a local minimizer of a NP-hard optimization problem is still NP-hard [closed]

I was wondering if for a NP-hard optimization problem, I only want to find its local minimizer, is it still NP-hard or NP-hard is only true when trying to find a global minimizer?
175 views

### Can we say that this problem is NP-hard?

I have an optimization problem of the form: \begin{align} &\text{maximize}\quad f(\mathbf{x}) = \dfrac{\sum\limits_{n=1}^{N}x_na_n}{1+\sum\limits_{n=1}^{N}x_nb_n}\\ & \text{subject to}\quad \...
245 views

### On Knot Equivalence problem statement

How is the knot equivalence problem represented? By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...
137 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
165 views

### NP-hardness of finding maximum of minimum element in diagonal of a matrix

For $A = \{a_{ij}\} \in R^{n\times n}$, is finding $$\max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i}$$ NP-hard?
96 views

### Surd Partition Problem

Could the following "Surd Partition" problem be NP complete? Note that if the square roots are omitted in the following then the problem is well known to have a polynomial solution. Surd Partition ...
336 views

### Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time: Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...
276 views

### reduction to np hard ordering problem

I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm. My problem is: I have M auctions and in each auction I have N ...
2k views

### What impact would P=BQP have on NP?

Assuming P=BQP (ie we have polynomial time algorithms to solve all BQP problems) can we use it to prove that P=NP? The argument is that since we have the Grover's algorithm which can solve NP ...
2k views

### NP-hard problems in linear algebra and real analysis [closed]

I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent. I would thus like to collect in this thread a list of ...
432 views

### Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge$ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
164 views

### Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?