<p>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 <em>trivial</em> or not is undecidable, whereas this particular task is trivial in the other mentioned formats).</p>

<p>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 <em>property</em> of the input, rather than a the <em>format</em> of the input that is affecting complexity here. But I thought I'd mention it anyways.)</p>

CC BY-SA 3.0
2015-12-08T05:17:27.493Z
2015-12-08T05:17:27.493Z
Joshua Grochow
<p>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>

<ul>
<li><p><strong>P</strong> for deterministic automaton (more precisely <strong>NL</strong>-complete)</p></li>
<li><p><strong>PSPACE</strong>-complete for nondeterministic automaton or regular expression</p></li>
<li><p><strong>EXPSPACE</strong>-complete for regular expression with squaring operation.</p></li>
<li><p><strong>NONELEMENTARY</strong> for Monadic Second-Order (MSO) formula.</p></li>
</ul>

CC BY-SA 3.0
2015-12-08T11:02:54.617Z
2015-12-08T13:01:20.947Z
2015-12-08T13:01:20.947Z
Denis
<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2011-07-13T22:23:44.717Z
2011-07-13T22:23:44.717Z
Suresh Venkat
<p>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})$.</p>

CC BY-SA 3.0
2014-02-24T12:13:46.407Z
Interesting.  For others who find this answer, here is an entrance to the literature: "Group-theoretic Algorithms for Matrix Multiplication" by Cohn et al.
Sam Nead
CC BY-SA 3.0
2011-07-13T23:38:38.030Z
2011-07-13T23:38:38.030Z
v s
<p>The most obvious example is Subset-sum problem:</p>

<p>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$.</p>

<p>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)$.</p>

<p>We know that this problem is an NP-complete problem.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-14T00:27:37.013Z
2011-07-14T00:27:37.013Z
Amir
<p>Stark example of this phenomena is the fact that it is <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW84/GW84.pdf" rel="nofollow">NP-complete to decide if undirected graph has a triangle</a> when the input graph is succinctly represented using small circuits. The problem is in P for adjacency matrix representation.</p>

CC BY-SA 3.0
2015-12-08T20:57:15.187Z
2015-12-08T20:57:15.187Z
Mohammad Al-Turkistany
<p>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) </p>

<p>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?</p>

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

CC BY-SA 3.0
2011-07-12T13:58:27.157Z
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.
yatima2975
CC BY-SA 3.0
2011-07-12T14:18:14.690Z
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.
George
CC BY-SA 3.0
2011-07-12T15:53:24.030Z
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".
Kaveh
CC BY-SA 3.0
2011-07-18T13:26:19.430Z
@George: that's a much better example! You should post that as an answer.
yatima2975
<cc.complexity-theory>
Data representation affecting problem complexity
XOPs
# Data representation affecting problem complexity

(Asked by: username_0 on 2011-07-12)

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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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".  
> **username_1**: @username_2: that's a much better example! You should post that as an answer.  

---

## 6 answers

### Answer by username_4 on 2015-12-08. Score: 8

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.)


---

### Answer by username_6 on 2011-07-13. Score: 5

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.


---

### Answer by username_5 on 2015-12-08. Score: 4

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.


---

### Answer by username_7 on 2011-07-13. Score: 3

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})$.

> **Comments:**
> **username_8**: Interesting.  For others who find this answer, here is an entrance to the literature: "Group-theoretic Algorithms for Matrix Multiplication" by Cohn et al.  

---

### Answer by username_9 on 2011-07-14. Score: 2

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.


---

### Answer by username_10 on 2015-12-08. Score: 0

Stark example of this phenomena is the fact that it is [NP-complete to decide if undirected graph has a triangle](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW84/GW84.pdf) when the input graph is succinctly represented using small circuits. The problem is in P for adjacency matrix representation.


---

