5
$\begingroup$

According to wikipedia integer circuit in its simplest form is succinct representation of multivariate polynomial with integer coefficients. Decidability if an integer is represented by the integer circuit is an open problem.

Working only with integer circuits with gates $\times,+,-$ we got an argument that it is undecidable to check if integer is represented by the circuit.

Take undecidable diophantine equation $f(x_i)=0$. (If you want to work with non-negative solution, replace each $x_i$ with the sum of squares of four new variables).

Let $C_f$ be the integer circuit which computes $f$.

$C_f$ represents $0$ if $f(x_i)=0$ has a solution and by construction this is undecidable.

Does this prove integer circuit membership is undecidable?

(We don't use gates about set union, intersection and complement).

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Does the Wikipedia table on complexity scale with the cardinality of the set from which you draw your input integer? With the proof above you are asking if there is any integer solution; if you ask instead if there’s a solution from within a finite set, then maybe you get the complexity results listed in Wikipedia? $\endgroup$
    – Mark S
    Commented Oct 11, 2019 at 11:43
  • $\begingroup$ Maybe not. Travers linked in Wikipedia indicates that the inputs are members of the power set of $\mathbb{Z}$; I believe the size of the input is related to the complexity of the circuit evaluating $C_f$ and not of the elements of the power set of $\mathbb{Z}$. $\endgroup$
    – Mark S
    Commented Oct 11, 2019 at 12:03
  • $\begingroup$ @MarkS Thanks. Does size matter for decidability? The size maybe horribly large, but still finite. $\endgroup$
    – joro
    Commented Oct 11, 2019 at 13:01
  • 1
    $\begingroup$ You misunderstand the definition of the circuit membership problem. The circuits do not compute integers, but sets of integers. The problem is simply to evaluate the circuit on a given input. You are given a circuit, and for each input node, a (finite) set of integers; then each node of the circuit is associated to a specific set of integers, and you are supposed to compute the set associated to the output node. ... $\endgroup$
    – Emil Jeřábek
    Commented Oct 11, 2019 at 14:35
  • 1
    $\begingroup$ Here is an interesting twist: if a polynomial $f$ is given by a read-once arithmetic formula (which means that for each $+$ or $\times$ gate in the circuit, the two input nodes compute polynomials in disjoint sets of variables), then we can express the set of integers represented by this polynomial by a circuit obtained from the given one just by evaluating each variable to $\mathbb Z$ (which can be constructued as $-(\{0\}\cap\{1\})$). In particular, the circuit membership problem is at least as hard as solvability of multilinear polynomials. $\endgroup$
    – Emil Jeřábek
    Commented Oct 11, 2019 at 15:02

0

Reset to default

You must log in to answer this question.