28 questions linked to/from Problems Between P and NPC
340 views

### Complexity of Localization in Wireless Networks

Let distinct points $1 ... n$ sit in $\mathbb{R}^2$. We say points $i$ and $j$ are neighbors if $|i-j| < 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, ...
733 views

### GI-hard graph problem not known to be $NP$-complete

Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A ...
1k views

### Is there a problem in ZPP not yet in P?

Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P ...
311 views

### Complexity of summing up integral powers

Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem? It is clear from Faulhaber's ...
308 views

### NPI-candidate hereditary graph property?

A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover, a number of nontrivial general facts are ...
1k views

### Complexity of computing shortest paths in the plane with polygonal obstacles

Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
754 views

### NP-Hardness of a special case of orthogonal packing problem

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used ...
596 views

### Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs

Kastelyn in the 1960's continuing Onsanger's work on the Ising model, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs. Has a similar algorithm ...
132 views

### What's the complexity of factoring over a set of generators (say in $GL_2$)?

In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know ...
852 views

### Complexity class of this problem?

I am trying to understand to which complexity class the following problem belongs: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients ...
674 views

### open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?
Let $R(v_{\bullet}, w_{\bullet})$ be some $P$-time computable relation between two binary strings $v_{\bullet}$ and $w_{\bullet}$. $NP$ problems are problems of the form: Given $v_{\bullet}$, ...
I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following: There is a value \$\...