-4
votes
1answer
177 views

An algorithm and symbolic manipulation for IF-THEN-ELSE [closed]

CONCLUSION (so far)  Look at the parentheses theorem and at the comments below the question(s) :-) As for now, only Dan Peterson has truly addressed the issue. Q1   Does there exists an ...
19
votes
0answers
339 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
9
votes
1answer
287 views

Can Tarski decide constructibility in elementary geometry?

Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction? The answer does ...
2
votes
3answers
263 views

existence of equivalence checking algorithm

Set D : Set of decision algorithms X∈D if and only if X is an Turing machine algorithm with finite length takes one input i, binary number X(i)=0 or X(i)=1 or X(i) runs ...
6
votes
1answer
363 views

Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
15
votes
4answers
764 views

Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem: Show, for all integers $1 \leq i \leq k$, that the univariate ...
2
votes
1answer
468 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
3
votes
2answers
822 views

Fast algorithms for addition and multiplication of Zhegalkin polynomials

Hello to all, I'm interested in fast algorithms for addition and multiplication of Zhegalkin polynomials. For example, let $f_1(x_1, x_2, x_3) = 1+x_1+x_2x_3$ $f_2(x_1, x_2, x_3) = x_1+x_3$ I'd ...
7
votes
2answers
860 views

Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
8
votes
3answers
675 views

Definition of relativization of complexity class

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$? Usually, these classes and their relativizations seem to be defined in an ad-hoc ...
23
votes
2answers
992 views

Is it decidable whether or not a collection of integer matrices generates a free group?

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
6
votes
1answer
421 views

post correspondence problem variant

Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...
6
votes
2answers
1k views

Horn clauses and satisfiability

It is well known that satisfiability of Horn formulae can be checked in polynomial time using unit propagation. But suppose we relax the condition for horn clauses from at most one un-negated ...
18
votes
3answers
2k views

Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...