On Positive Computation

Eduardo Skapinakis

REVIEW

On Positive Computation

Eduardo Skapinakis

Computational Complexity · Submitted 6 Nov 2026 · 38 references

Pith's verdict: A real completeness theory for mNP under positive reductions, with the mCSAT half checked out; the HCP gadget and mTQC proof are genuine gaps, but the paper deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 9, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 7 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2611.09622 (version 1)

Pith IDX5MBLJ4R, Pith's permanent record of this paper and its review

CitationEduardo Skapinakis. "On Positive Computation." arXiv:2611.09622 (2026). https://pith.science/paper/X5MBLJ4R

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Read this if you work on monotone or positive computation. It is a real completeness theory for mNP under positive many-to-one reductions, stronger than the monotone projection translations used before, and the mCSAT half is solid. The genuinely new machinery is Theorem 3.10 (predictable FP functions can be implemented positively on the interleaved input ⋄x), the size-based pairing, and a circuit encoding that makes EVAL a monotone formula of the circuit code bits. I checked the mCSAT chain (Theorem 4.1, Lemma 5.8, Theorem 5.9) in detail and it holds. Proposition 5.4 and the P≠NP sufficient condition in Theorem 5.5 are also correct as stated. No fitted parameters, no circular reasoning, and the self-citation to [25] concerns foundational facts the paper re-derives.

The soft spots are real, and the authors know those parts are sketchy. Theorem 5.13 modifies the Kleinberg-Tardos gadget by intersecting x(|x|-i) into the left-to-right edges of variable block v_{2i-1}, and the load-bearing local soundness claim is one sentence: that any Hamiltonian cycle must then traverse that block right-to-left. What is missing is a proof that deleting those edges creates no new Hamiltonian cycles, destroys none through clause or middle vertices, and interacts with the rest of the reduction exactly as claimed. That claim carries HCP mNP-completeness and, through HCP∉posP, the later use of HCP in Lemma 7.1 and Theorem 7.3. I think the claim is probably true, since the blocks are modular, but probably true is not a proof. The other gap is Theorem 6.7: mTQC mPSPACE-completeness is only sketched, and the non-relativizing oracle in Theorem 6.8 depends on it. The weak diagonalization in Section 7 is standard and works once HCP∉posP is granted, although the paper leaves that corollary implicit.

This is not desk-reject material. The reduction notion, the mCSAT completeness proof, and the sufficient condition for P≠NP are substantial, and the two missing proofs are localized and likely repairable. I would send it to a competent referee and ask that the HCP gadget proof and the mTQC proof be completed before acceptance, or that the claims be scaled back accordingly.

Referee report

Significance

If the central claims hold, the paper contributes a genuinely stronger completeness theory for mNP: two natural monotone NP-complete problems are complete under posFP reductions rather than only under the weaker monotone projection translations, and the non-relativization result is an interesting counterpoint to the standard separation posP ⊊ mNP. The mCSAT chain is carefully engineered: the EVAL construction, the encoding of χ≤ with hardwired x-bits, and the size arithmetic of the reduction are worked out in detail, and the paper relies on external published benchmarks rather than fitted parameters. However, two load-bearing proofs are incomplete as written: the modified Kleinberg-Tardos gadget in Theorem 5.13 and the sketched proof of Theorem 6.7. Since HCP ∉ posP and the diagonalization in Section 7 depend on Theorem 5.13, the paper does not yet fully establish its headline results.

Major objections (3)

[Section 5.2, Theorem 5.13] The mNP-completeness of HCP rests on a one-sentence local-soundness assertion. After the Kleinberg-Tardos graph is built, the proof deletes the edges representing the left-to-right traversal of the block of v_{2i-1} and states: 'This ensures that if a cycle through G exists, it must take the right to left direction on the block.' The cited reference [18] supports the original gadget, but the edge intersection is a novel modification and is not covered by that citation. The proof must show: (i) the deleted horizontal edges are not also used by clause or middle-vertex connections in a way that allows a Hamiltonian cycle to enter the block left-to-right through a clause; (ii) deleting those edges creates no unintended Hamiltonian cycles through clause or middle vertices; (iii) when x(|x|-i)=1 the original cycles survive, and whenever the formula has a satisfying assignment with v_{2i-1}=0, a right-to-left traversal still visits every clause vertex exactly once. Without this, Theorem 5.13 is unproved, and the consequences HCP ∉ posP and the use of HCP in Lemma 7.1 and Theorem 7.3 do not follow. The base Kleinberg-Tardos reduction is also only described as 'similar' to [18, Chapter 8]; please specify the graph construction exactly and prove its soundness for arbitrary CNF formulas.
[Section 6.2, Theorem 6.7] mTQC is claimed to be mPSPACE-complete under posFP many-one reductions, but the proof is explicitly only a sketch. This is load-bearing for the non-relativization theorem: Theorem 6.8 uses mTQC as the oracle and needs the completeness statement to conclude mPSPACE ⊆ posP^A. Please supply the details that are only asserted: the normalization of an arbitrary mPSPACE set as a polynomial-time alternating machine with an initial existential guess of y ≤ x; the exact construction of the circuit E_x^n and the quantifier word k(x); and the verification that x ↦ ⟨⌜E_x^n⌝, k(x)⟩ is a posFP many-one reduction. The phrase 'just as in Theorem 5.9' hides the hardwiring of x into the circuit and the handling of alternating quantifiers, both of which are nontrivial for positivity.
[Section 7, Theorem 7.3] The diagonalization argument should state explicitly that it uses HCP ∉ posP as an input, and that this fact is obtained in the paper from the mNP-completeness of HCP together with the known separation posP ⊊ mNP. Lemma 7.1 only shows that a monotone function outside posP is not a finite variant of a posP function; Theorem 7.3 then applies this to HCP. This dependency is legitimate if Theorem 5.13 is repaired, but it should be stated so that the reader sees that Theorem 7.3 is conditional on the HCP completeness proof.

Minor objections (7)

[Section 3.1, Definition 3.5] The functions P1 and P2 are specified by their values on CANTOR(x,y), but the unpairing functions (·)_0 and (·)_1 are applied to arbitrary words. Please define P1 and P2 on all inputs, or state explicitly that their values outside the image of CANTOR are arbitrary and chosen so that the functions are in posFP.
[Section 5.2, Definition 5.12] The positive function CYCLE is not defined; the text only describes it informally. Please give its code-level definition, or at least state the exact formula obtained from Theorem 3.10, since HCP ∈ mNP depends on this function.
[Section 5.1, Lemma 5.8] The circuit is said to compute 'z ↦ χ≤(z,x)' for arbitrary z, but χ≤ was defined in Lemma 3.11 only for pairs of the form (⋄y, y) with |⋄y| = 2|y|. The circuit actually computes ∧_i (z(2i) ∨ x(i)), which equals χ≤(⋄y, x) when z = ⋄y. Please align the notation.
[Section 7, Lemma 7.1] The line 'For simplicity, assume that they only differ in x~ ∈ {0,1}^n' is misleading because the subsequent construction already handles arbitrary finite variants; please rephrase it as a warm-up or remove it. Also specify the convention when a length n has no true point, i.e., when b_n = 0.
[Section 7, Theorem 7.3] The definition of f uses f(x−1), which treats x as a natural number, while x was introduced as a word. Please state explicitly that words are identified with their binary numerals for the purpose of the enumeration.
[Section 6, Theorem 6.8] The oracular classes posP^A, mNP^A, and mPSPACE^A are used without formal definitions. Please define these relativized classes before the collapse argument, since the monotonicity of the oracle and of the positive machines is central to the proof.
[Abstract and Theorem 5.5] The abstract's sufficient condition for P ≠ NP is phrased as 'if this holds for all (monotone) mNP-complete problems,' while Theorem 5.5 assumes the existence of a positive encoding Ξ for each monotone NP-complete A. A sentence explaining that the abstract statement is the special case Ξ = identity would prevent a misreading.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Monotone Circuit Satisfiability and Hamiltonian Cycle are shown complete for mNP under new positive reductions, and posP ⊊ mNP is shown not to relativize while a weak diagonalization proof exists.

The reading

This paper works in monotone computing, where the underlying operations only go in one direction: turning a 0 into a 1 can never turn a true statement into a false one. In this world computers cannot directly use negation, so questions like "is this circuit satisfiable?" behave differently than for ordinary computers. The author defines a new kind of translation between such problems, called a positive reduction, which respects this monotone structure.

The main results are that two well-known NP-complete problems, a monotone version of circuit satisfiability and the Hamiltonian cycle problem, are complete for the monotone class mNP even under these stricter positive reductions. The proofs rely on a trick: any ordinary polynomial-time computation can be simulated by a positive computation, provided the input is presented together with its own negation, interleaved bit by bit. Since many parts of the standard reductions only need the size of the input, this trick can be pushed through the Tseitin transform and the usual circuit-to-graph construction.

The paper also studies oracles. It constructs a monotone oracle relative to which the classes posP and mNP become equal, even though they are known to be different in the real world. This means the known separation is not provable by a relativizing argument. At the same time, the author adapts Kozen's classic argument to build an enumeration of posP whose diagonal is exactly the Hamiltonian cycle problem, a weak diagonalization witnessing the separation.

Extended reading notes

Core claim

Theorem 5.9 states that mCSAT is mNP-complete under posFP many-to-one reductions, and Theorem 5.13 states the same for the Hamiltonian Cycle Problem. Theorem 5.5 states that if every monotone NP-complete problem A admits a positive encoding Ξ with Ξ(A) mNP-complete under posFP reductions, then P ≠ NP. If correct, the paper establishes a completeness theory for mNP under a reduction notion stronger than the monotone projection translations used previously, plus a new sufficient condition for P ≠ NP.

Load-bearing premise

The load-bearing premise is that the modified Kleinberg-Tardos gadget in Theorem 5.13 behaves as claimed: intersecting the input bit x(|x|-i) into the adjacency matrix entries of the left-to-right path of variable block v_{2i-1} forces every Hamiltonian cycle to traverse that block right-to-left (representing v_{2i-1} = 0), without creating or destroying unintended Hamiltonian cycles. The paper asserts this in one sentence ("This ensures that if a cycle through G exists, it must take the right to left direction on the block of v_{2i-1}") without a full proof. HCP mNP-completeness depends on it, and via the corollary HCP ∉ posP, so does the diagonalization in Theorem 7.3. A second, smaller fragility is Theorem 6.7 (mTQC mPSPACE-completeness), which carries the non-relativization theorem and is only sketched.

Original abstract

We introduce new notions of reducibility for monotone classes and show that a monotone version of Circuit Satisfiability and the Hamiltonian Cycle Problem are complete for $mNP$, even under positive reductions (which are not the same as monotone reductions). If this holds for all (monotone) $mNP$-complete problems - that they are also so complete for $mNP$ -, then $P\neq NP$. We introduce positive models of relativized computation and show that the separation $posP\subsetneq mNP$ does not relativize, even when oracles are restricted to monotone sets. Yet, there is a (weak) diagonalization proof that $posP\subsetneq mNP$.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-09: 1 request, 3,698 input tokens.

What the abstract itself states, as probabilities: claims first 0.09 · states limitation 0.66 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.06 · compares with prior results 0.68 · mentions code or data availability 0.01.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We introduce new notions of reducibility for monotone classes and show that a monotone version of Circuit Satisfiability and the Hamiltonian Cycle Problem are complete for $mNP$, even under positive reductions (which are not the same as monotone reductions). If this holds for all (monotone) $mNP$-complete problems - that they are also so complete for $mNP$ -, then $P\neq NP$. We introduce positive models of relativized computation and show that the separation $posP\subsetneq mNP$ does not relativize, even when oracles are restricted to monotone sets. Yet, there is a (weak) diagonalization proof that $posP\subsetneq mNP$.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We introduce new notions of reducibility for monotone classes and show that a monotone version of Circuit Satisfiability and the Hamiltonian Cycle Problem are complete for $mNP$, even under positive reductions (which are not the same as monotone reductions).	contribution 0.65	0.95	0.38	asserted 1.00
s1	If this holds for all (monotone) $mNP$-complete problems - that they are also so complete for $mNP$ -, then $P\neq NP$.	interpretation 0.93	0.35	0.29	hedged possibility 0.57
s2	We introduce positive models of relativized computation and show that the separation $posP\subsetneq mNP$ does not relativize, even when oracles are restricted to monotone sets.	contribution 0.58	0.93	0.21	asserted 1.00
s3	Yet, there is a (weak) diagonalization proof that $posP\subsetneq mNP$.	result 0.83	0.72	0.18	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (38)

[25]

I. Oitavem and E. Skapinakis. A recursion-theoretic characterization of monotone NP.Archive for Mathematical Logic, 2026

View on Pith 2026
[18]

J. Kleinberg and E. Tardos.Algorithm Design. Addison-Wesley, 2005.https://www.cs. princeton.edu/~wayne/kleinberg-tardos/

View on Pith 2005
[1]

S. Aaronson. Oracles are subtle but not malicious. In21st Annual IEEE Conference on Computational Complexity (CCC’06), pages 15–pp. IEEE, 2006

View on Pith 2006
[2]

S. Arora and B. Barak.Computational complexity: a modern approach. Cambridge University Press, 2016

View on Pith 2016
[3]

S. Arora, R. Impagliazzo, and U. Vazirani. Relativizing versus nonrelativizing techniques: the role of local checkability, 1991

View on Pith 1991
[4]

T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question.SIAM Journal on computing, 4(4):431–442, 1975

View on Pith 1975
[5]

J. Balcazar and J. Diaz. A note on a theorem by ladner.Information Processing Letters, 15(2):84–86, 1982

View on Pith 1982
[6]

J. L. Balc´ azar, J. D ´ ıaz, and J. Gabarr´ o.Structural complexity. Springer Science & Business Media, 1988

View on Pith 1988
[7]

S. R. Buss.Bounded arithmetic. Princeton University, 1985

View on Pith 1985
[8]

A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation.Journal of the ACM, 28(1):114–133, 1981

View on Pith 1981
[9]

S. A. Cook. The complexity of theorem-proving procedures. InProceedings of the third annual ACM symposium on Theory of computing, pages 151–158, 1971

View on Pith 1971
[10]

A. Das. From positive and intuitionistic bounded arithmetic to monotone proof complexity. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 126–135, 2016. 15

View on Pith 2016
[11]

A. Das and I. Oitavem. A recursion-theoretic characterisation of the positive polynomial-time functions. In27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Schloss Dagstuhl-Leibniz-Zentrum f¨ ur Informatik, 2018

View on Pith 2018
[12]

L. Fortnow. The role of relativization in complexity theory.Bulletin of the European Associ- ation for Theoretical Computer Science, 1994

View on Pith 1994
[13]

L. Fortnow. Diagonalization.Bulletin of the European Association for Theoretical Computer Science, 71:102–113, 2000

View on Pith 2000
[14]

L. M. Goldschlager. The monotone and planar circuit value problems are log space complete for P.ACM sigact news, 9(2):25–29, 1977

View on Pith 1977
[15]

M. Grigni and M. Sipser. Monotone complexity.Boolean function complexity, 169:57–75, 1992

View on Pith 1992
[16]

R. Impagliazzo, V. Kabanets, and A. Kolokolova. An axiomatic approach to algebrization. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 695–704, 2009

View on Pith 2009
[17]

M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. InProceedings of the twentieth annual ACM symposium on Theory of computing, pages 539–550, 1988

View on Pith 1988
[19]

D. Kozen. Indexing of subrecursive classes. InProceedings of the tenth annual ACM symposium on Theory of computing, 1978

View on Pith 1978
[20]

R. E. Ladner. On the structure of polynomial time reducibility.Journal of the ACM (JACM), 22(1):155–171, 1975

View on Pith 1975
[21]

C. Lautemann, T. Schwentick, and I. A. Stewart. On positive P. InProceedings of Computa- tional Complexity, pages 162–170. IEEE, 1996

View on Pith 1996
[22]

C. Lautemann, T. Schwentick, and I. A. Stewart. Positive versions of polynomial time.Infor- mation and Computation, 147(2):145–170, 1998

View on Pith 1998
[23]

L. A. Levin. Universal sequential search problems.Problemy peredachi informatsii, 9(3):115– 116, 1973

View on Pith 1973
[24]

A. Nash, R. Impagliazzo, and J. B. Remmel. Universal languages and the power of diagonal- ization. In18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 337–346, 2003

View on Pith 2003
[26]

R. Raz and P. McKenzie. Separation of the monotone nc hierarchy. InProceedings 38th Annual Symposium on Foundations of Computer Science, pages 234–243. IEEE, 1997

View on Pith 1997
[27]

A. A. Razborov. Lower bounds for the monotone complexity of some Boolean functions. In Doklady Akademii Nauk SSSR, volume 281, pages 798–801, 1985. English translation in Soviet Mathematics. Doklady. 31:354–357 (1985)http://mi.mathnet.ru/dan9192

View on Pith 1985
[28]

A. A. Razborov. Lower bounds on monotone complexity of the logical permanent.Matematich- eskie Zametki, 37:485–493, 1985. English translation in Mathematical Notes of the Academy of Sciences of the USSR, 37(6):887–900 (1985)http://mi.mathnet.ru/mzm5393

View on Pith 1985
[29]

D. Sannella, M. Fourman, H. Peng, and P. Wadler.Introduction to Computation. Springer Cham, 2022. 16

View on Pith 2022
[30]

I. Stewart. Methods for proving completeness via logical reductions.Theoretical Computer Science, 118(2):193–229, 1993

View on Pith 1993
[31]

I. A. Stewart. Logical description of monotone NP problems.Journal of Logic and Computa- tion, 4(4):337–357, 1994

View on Pith 1994
[32]

I. A. Stewart. Complete problems for monotone NP.Theoretical computer science, 145(1- 2):147–157, 1995

View on Pith 1995
[33]

L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. InProceedings of the fifth annual ACM symposium on Theory of computing, pages 1–9, 1973

View on Pith 1973
[34]

T. Strahm. Theories with self-application and computational complexity.Information and Computation, 185(2):263–297, 2003

View on Pith 2003
[35]

´E. Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8:141–142, 1988

View on Pith 1988
[36]

J. Tor´ an. Complexity classes defined by counting quantifiers.Journal of the ACM (JACM), 38(3):752–773, 1991

View on Pith 1991
[37]

G. S. Tseitin. On the complexity of derivation in propositional calculus. InAutomation of reasoning: 2: Classical papers on computational logic 1967–1970, pages 466–483. Springer, 1983

View on Pith 1967
[38]

C. Wrathall. Complete sets and the polynomial-time hierarchy.Theoretical Computer Science, 3(1):23–33, 1976. Appendix 8.1 Positive Turing machines and accepting states Recall that, in [21, 22], positive Turing machines were defined having an accepting and rejecting state, whereas in [11] only ahaltingstate is considered. We give an example as to why this ...

View on Pith 1976

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [25]

I. Oitavem and E. Skapinakis. A recursion-theoretic characterization of monotone NP.Archive for Mathematical Logic, 2026

View on Pith 2026

[2] [18]

J. Kleinberg and E. Tardos.Algorithm Design. Addison-Wesley, 2005.https://www.cs. princeton.edu/~wayne/kleinberg-tardos/

View on Pith 2005

[3] [1]

S. Aaronson. Oracles are subtle but not malicious. In21st Annual IEEE Conference on Computational Complexity (CCC’06), pages 15–pp. IEEE, 2006

View on Pith 2006

[4] [2]

S. Arora and B. Barak.Computational complexity: a modern approach. Cambridge University Press, 2016

View on Pith 2016

[5] [3]

S. Arora, R. Impagliazzo, and U. Vazirani. Relativizing versus nonrelativizing techniques: the role of local checkability, 1991

View on Pith 1991

[6] [4]

T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question.SIAM Journal on computing, 4(4):431–442, 1975

View on Pith 1975

[7] [5]

J. Balcazar and J. Diaz. A note on a theorem by ladner.Information Processing Letters, 15(2):84–86, 1982

View on Pith 1982

[8] [6]

J. L. Balc´ azar, J. D ´ ıaz, and J. Gabarr´ o.Structural complexity. Springer Science & Business Media, 1988

View on Pith 1988

[9] [7]

S. R. Buss.Bounded arithmetic. Princeton University, 1985

View on Pith 1985

[10] [8]

A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation.Journal of the ACM, 28(1):114–133, 1981

View on Pith 1981

[11] [9]

S. A. Cook. The complexity of theorem-proving procedures. InProceedings of the third annual ACM symposium on Theory of computing, pages 151–158, 1971

View on Pith 1971

[12] [10]

A. Das. From positive and intuitionistic bounded arithmetic to monotone proof complexity. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 126–135, 2016. 15

View on Pith 2016

[13] [11]

A. Das and I. Oitavem. A recursion-theoretic characterisation of the positive polynomial-time functions. In27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Schloss Dagstuhl-Leibniz-Zentrum f¨ ur Informatik, 2018

View on Pith 2018

[14] [12]

L. Fortnow. The role of relativization in complexity theory.Bulletin of the European Associ- ation for Theoretical Computer Science, 1994

View on Pith 1994

[15] [13]

L. Fortnow. Diagonalization.Bulletin of the European Association for Theoretical Computer Science, 71:102–113, 2000

View on Pith 2000

[16] [14]

L. M. Goldschlager. The monotone and planar circuit value problems are log space complete for P.ACM sigact news, 9(2):25–29, 1977

View on Pith 1977

[17] [15]

M. Grigni and M. Sipser. Monotone complexity.Boolean function complexity, 169:57–75, 1992

View on Pith 1992

[18] [16]

R. Impagliazzo, V. Kabanets, and A. Kolokolova. An axiomatic approach to algebrization. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 695–704, 2009

View on Pith 2009

[19] [17]

M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. InProceedings of the twentieth annual ACM symposium on Theory of computing, pages 539–550, 1988

View on Pith 1988

[20] [19]

D. Kozen. Indexing of subrecursive classes. InProceedings of the tenth annual ACM symposium on Theory of computing, 1978

View on Pith 1978

[21] [20]

R. E. Ladner. On the structure of polynomial time reducibility.Journal of the ACM (JACM), 22(1):155–171, 1975

View on Pith 1975

[22] [21]

C. Lautemann, T. Schwentick, and I. A. Stewart. On positive P. InProceedings of Computa- tional Complexity, pages 162–170. IEEE, 1996

View on Pith 1996

[23] [22]

C. Lautemann, T. Schwentick, and I. A. Stewart. Positive versions of polynomial time.Infor- mation and Computation, 147(2):145–170, 1998

View on Pith 1998

[24] [23]

L. A. Levin. Universal sequential search problems.Problemy peredachi informatsii, 9(3):115– 116, 1973

View on Pith 1973

[25] [24]

A. Nash, R. Impagliazzo, and J. B. Remmel. Universal languages and the power of diagonal- ization. In18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 337–346, 2003

View on Pith 2003

[26] [26]

R. Raz and P. McKenzie. Separation of the monotone nc hierarchy. InProceedings 38th Annual Symposium on Foundations of Computer Science, pages 234–243. IEEE, 1997

View on Pith 1997

[27] [27]

A. A. Razborov. Lower bounds for the monotone complexity of some Boolean functions. In Doklady Akademii Nauk SSSR, volume 281, pages 798–801, 1985. English translation in Soviet Mathematics. Doklady. 31:354–357 (1985)http://mi.mathnet.ru/dan9192

View on Pith 1985

[28] [28]

A. A. Razborov. Lower bounds on monotone complexity of the logical permanent.Matematich- eskie Zametki, 37:485–493, 1985. English translation in Mathematical Notes of the Academy of Sciences of the USSR, 37(6):887–900 (1985)http://mi.mathnet.ru/mzm5393

View on Pith 1985

[29] [29]

D. Sannella, M. Fourman, H. Peng, and P. Wadler.Introduction to Computation. Springer Cham, 2022. 16

View on Pith 2022

[30] [30]

I. Stewart. Methods for proving completeness via logical reductions.Theoretical Computer Science, 118(2):193–229, 1993

View on Pith 1993

[31] [31]

I. A. Stewart. Logical description of monotone NP problems.Journal of Logic and Computa- tion, 4(4):337–357, 1994

View on Pith 1994

[32] [32]

I. A. Stewart. Complete problems for monotone NP.Theoretical computer science, 145(1- 2):147–157, 1995

View on Pith 1995

[33] [33]

L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. InProceedings of the fifth annual ACM symposium on Theory of computing, pages 1–9, 1973

View on Pith 1973

[34] [34]

T. Strahm. Theories with self-application and computational complexity.Information and Computation, 185(2):263–297, 2003

View on Pith 2003

[35] [35]

´E. Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8:141–142, 1988

View on Pith 1988

[36] [36]

J. Tor´ an. Complexity classes defined by counting quantifiers.Journal of the ACM (JACM), 38(3):752–773, 1991

View on Pith 1991

[37] [37]

G. S. Tseitin. On the complexity of derivation in propositional calculus. InAutomation of reasoning: 2: Classical papers on computational logic 1967–1970, pages 466–483. Springer, 1983

View on Pith 1967

[38] [38]

C. Wrathall. Complete sets and the polynomial-time hierarchy.Theoretical Computer Science, 3(1):23–33, 1976. Appendix 8.1 Positive Turing machines and accepting states Recall that, in [21, 22], positive Turing machines were defined having an accepting and rejecting state, whereas in [11] only ahaltingstate is considered. We give an example as to why this ...

View on Pith 1976