5
$\begingroup$

Given some problem, could you have a situation where the problem is shown to be in P, assuming you start with a particular representation of the problem and some data structures, but that if the problem data was represented in some other way then the problem would become NP? (or some other complexity classes)

In other words have any problems been stated to be in P when this depends on the input data being formatted in a way that a would-be algorithm-user wouldn't necessarily have available so the complexity of the problem becomes drastically changed by needing to convert the data first?

This question comes from wondering how knots can be represented and wondered how this would affect comparing whether two knots are the same?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Well, there's the unary vs binary encoding, but that's a bit too trivial. If you assume the conversion between the two formats is polynomial, P and NP are robust under that. $\endgroup$ Commented Jul 12, 2011 at 13:58
  • 7
    $\begingroup$ Consider SAT: If you are given a formula in CNF the problem is NP-complete; If you are given a formula in DNF the problem can be solved in polynomial time. However, the formula of DNF is exponentially larger than the formula in CNF. $\endgroup$ Commented Jul 12, 2011 at 14:18
  • 2
    $\begingroup$ The complexity of a problem strongly depends on the encoding of inputs/outputs, e.g. the complexity can be reduced using padded inputs. Also Google for "weakly NP-complete". $\endgroup$ Commented Jul 12, 2011 at 15:53
  • $\begingroup$ @George: that's a much better example! You should post that as an answer. $\endgroup$ Commented Jul 18, 2011 at 13:26

6 Answers 6

Reset to default
8
$\begingroup$

Although not (yet) getting all the way down to $\mathsf{P}$, Group Isomorphism and other algebraic problems can depend heavily on the format of the input, in a way that is far more subtle than merely padding. For example, when the groups are given by multiplication tables, there is a trivial $n^{\log n + O(1)}$-time algorithm to test isomorphism. When the groups are given by generating sets (say, of permutations, or of matrices over finite fields), there are slightly sub-exponential algorithms, but the problems are at least as hard as Graph Isomorphism. When the groups are given by generators and relations, the problem is undecidable (indeed, when given by generators and relations, even telling if the group is trivial or not is undecidable, whereas this particular task is trivial in the other mentioned formats).

Another algebraic example is provided by Grobner bases. Most questions about ideals in polynomial rings become comparatively easy if you're given a Grobner basis for the ideal instead of an arbitrary generating set. But computing a Grobner basis is $\mathsf{EXPSPACE}$-complete. (This is perhaps not as good an example, since it is a property of the input, rather than a the format of the input that is affecting complexity here. But I thought I'd mention it anyways.)

Improve this answer
$\endgroup$
5
$\begingroup$

Related to the DNF/CNF formulation of SAT is the H-rep vs V-rep representation of a polytope for integer programming. If I give you all the vertices, IP can be solved in linear time. But the number of vertices is exponential in the number of constraints, which is the usual way the IP is presented.

So the answer to your question is YES. In the case of knot representation, the question sounds interesting, and maybe you could do a specific followup question on the knot problem directly.

Improve this answer
$\endgroup$
4
$\begingroup$

The complexity of deciding equality of regular languages (and many other problems on regular languages) varies a lot depending on the system of representation:

  • P for deterministic automaton (more precisely NL-complete)

  • PSPACE-complete for nondeterministic automaton or regular expression

  • EXPSPACE-complete for regular expression with squaring operation.

  • NONELEMENTARY for Monadic Second-Order (MSO) formula.

Improve this answer
$\endgroup$
3
$\begingroup$

There is an example from matrix multiplication but the complexity classes fall within $P$. Nevertheless there is a provable reduction in complexity. Looking at square matrices as elements for $\mathbb{Z}^{n^{2}}$ seems to not get you far to reduce complexity from $O(n^{3})$. However embedding the matrices as elements of $\mathbb{C}[G]$ for some appropriately constructed non-abelian group $G$, that is, looking at matrices as elements of the new algebraic object converts multiplication in these objects to point-wise product via Pontrjagin Duality thus reducing complexity from $O(n^{3})$ to a provable $O(n^{2.5})$ and a conjectural $O(n^{2})$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Interesting. For others who find this answer, here is an entrance to the literature: "Group-theoretic Algorithms for Matrix Multiplication" by Cohn et al. $\endgroup$ Commented Feb 24, 2014 at 12:13
2
$\begingroup$

The most obvious example is Subset-sum problem:

Given a set of integers $A= \{a_1,\cdots, a_n\}$ and an integer $S$, is there a subset of $A$ such that the sum of elements in it is equal to $S$.

If the target value, $S$, is given in its binary representation the size of problem description would be $\log (S)+n\log (S)=\theta(n\log S)$.

We know that this problem is an NP-complete problem.

But if all the integers are given in their unary representations, the size of input would be $\theta (nS)$. And the usual dynamic-programming approach (which runs in $O(nS)$) can solve the problem in polynomial time.

Improve this answer
$\endgroup$
0
$\begingroup$

Stark example of this phenomena is the fact that it is NP-complete to decide if undirected graph has a triangle when the input graph is succinctly represented using small circuits. The problem is in P for adjacency matrix representation.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.