论文标题
电路的满意度问题很小
Circuit Satisfiability Problem for circuits of small complexity
论文作者
论文摘要
考虑以下问题。 Turing Machine $ m $接受固定长度$ t $作为输入的字符串，运行不超过固定值$ n $，并保证会产生二进制输出。需要找到一个字符串$ x $，以便在$ t $，$ n $，$ m $的大小和$ m $的状态数量上有效地有效地有效地。该问题接近众所周知的电路满意度问题。电路满意度问题的差异在于，当减少到电路满足问题时，我们会获得具有丰富内部结构的电路（尤其是这些是小kolmogorov复杂性的电路）。 The proof system, operating with potential proofs of the fact that, for a given machine $M$, the string $X$ does not exist, is provided, its completeness is proved and the algorithm guaranteed to find a proof of the absence of the string $X$ in the case of its actual absence is presented (in the worst case, the algorithm is exponential, but in a wide class of interesting cases it works in polynomial time).我们提出了一种算法，以搜索字符串$ x $，该算法尚未对其效率进行测试，也不经过证明，并且可能需要在将来进行重大改进，因此可以将其视为一个想法。我们还讨论了解决类似于此问题的更复杂问题的第一步：Turing Machine $ m $，它接受两个字符串$ x $和$ y $的固定长度，并在不超过固定值的时间内运行；需要构建一个为任何字符串$ x $构建字符串$ y = n（x）$的算法$ n $，以便$ m（x，y）= 1 $（介绍中的详细信息）。
The following problem is considered. A Turing machine $M$, that accepts a string of fixed length $t$ as input, runs for a time not exceeding a fixed value $n$ and is guaranteed to produce a binary output, is given. It's required to find a string $X$ such that $M(X) = 1$ effectively in terms of $t$, $n$, the size of the alphabet of $M$ and the number of states of $M$. The problem is close to the well-known Circuit Satisfiability Problem. The difference from Circuit Satisfiability Problem is that when reduced to Circuit Satisfiability Problem, we get circuits with a rich internal structure (in particular, these are circuits of small Kolmogorov complexity). The proof system, operating with potential proofs of the fact that, for a given machine $M$, the string $X$ does not exist, is provided, its completeness is proved and the algorithm guaranteed to find a proof of the absence of the string $X$ in the case of its actual absence is presented (in the worst case, the algorithm is exponential, but in a wide class of interesting cases it works in polynomial time). We present an algorithm searching for the string $X$, for which its efficiency was neither tested, nor proven, and it may require serious improvement in the future, so it can be regarded as an idea. We also discuss first steps towards solving a more complex problem similar to this one: a Turing machine $M$, that accepts two strings $X$ and $Y$ of fixed length and running for a time that does not exceed a fixed value, is given; it is required to build an algorithm $N$ that builds a string $Y = N(X)$ for any string $X$, such that $M(X, Y) = 1$ (details in the introduction).
