Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Corrigendum to Affine Relativization

Corrigendum to Affine Relativization Unifying the Algebrization and Relativization Barriers BARIŞ AYDINLIOĞLU and ERIC BACH, University of Wisconsin—Madison CCS Concepts: • Theory of computation → Computational complexity and cryptography; Logic; Additional Key Words and Phrases: Algebrization, relativization, barriers, coding theory, interactive proofs ACM Reference format: Barış Aydınlıoğlu and Eric Bach. 2019. Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers. ACM Trans. Comput. Theory 11, 3, Article 16 (April 2019), 1 pages. https://doi.org/10.1145/3317693 It has come to our attention that in Reference [2], Theorem 8, and its continuation, Theorem 10, are proven using an argument that contradicts a theorem of Löb [3] (see Reference [1, Theorem 1] for an accessible account). Therefore, we retract these assertions. All of the other theorems/lemmas/propositions in the article remain valid, because they do not depend on the retracted assertions. The only implication of the retraction is that the reader cannot automatically conclude, from a theorem of the form “ψ relativizes (affinely),” that ψ has a proof that relativizes (affinely). In particular, the assertion in the “Summary of Results”, that certain statements have proofs that relativize affinely, does not automatically follow from the theorems given in Section 6. That assertion is still correct; however, because whenever we prove a statement of the form “ψ relativizes (affinely)” in the article, in particular in Section 6, we do in fact give a proof of ψ that relativizes (affinely). We thank Moritz Müller for pointing out this error. REFERENCES [1] Scott Aaronson. 2003. Is P versus NP formally independent? Bull. EATCS 81 (2003), 109–136. [2] Barış Aydınlıoğlu and Eric Bach. 2018. Affine relativization: Unifying the algebrization and relativization barriers. ACM Trans. Comput. Theory 10, 1 (2018), 1:1–1:67. DOI:https://doi.org/10.1145/3170704 [3] Martin Löb. 1955. Solution of a problem of Leon Henkin. J. Symbol. Logic 20, 2 (1955), 115–118. Authors’ addresses: B. Aydınlıoğlu and E. Bach, Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI; emails: {baris, bach}@cs.wisc.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Association for Computing Machinery. 1942-3454/2019/04-ART16 $15.00 https://doi.org/10.1145/3317693 ACM Transactions on Computation Theory, Vol. 11, No. 3, Article 16. Publication date: April 2019. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Corrigendum to Affine Relativization

Download PDF
1 page

Loading next page...
 
/lp/association-for-computing-machinery/corrigendum-to-affine-relativization-HeLdJHI0pO
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3317693
Publisher site
See Article on Publisher Site

Abstract

Unifying the Algebrization and Relativization Barriers BARIŞ AYDINLIOĞLU and ERIC BACH, University of Wisconsin—Madison CCS Concepts: • Theory of computation → Computational complexity and cryptography; Logic; Additional Key Words and Phrases: Algebrization, relativization, barriers, coding theory, interactive proofs ACM Reference format: Barış Aydınlıoğlu and Eric Bach. 2019. Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers. ACM Trans. Comput. Theory 11, 3, Article 16 (April 2019), 1 pages. https://doi.org/10.1145/3317693 It has come to our attention that in Reference [2], Theorem 8, and its continuation, Theorem 10, are proven using an argument that contradicts a theorem of Löb [3] (see Reference [1, Theorem 1] for an accessible account). Therefore, we retract these assertions. All of the other theorems/lemmas/propositions in the article remain valid, because they do not depend on the retracted assertions. The only implication of the retraction is that the reader cannot automatically conclude, from a theorem of the form “ψ relativizes (affinely),” that ψ has a proof that relativizes (affinely). In particular, the assertion in the “Summary of Results”, that certain statements have proofs that relativize affinely, does not automatically follow from the theorems given in Section 6. That assertion is still correct; however, because whenever we prove a statement of the form “ψ relativizes (affinely)” in the article, in particular in Section 6, we do in fact give a proof of ψ that relativizes (affinely). We thank Moritz Müller for pointing out this error. REFERENCES [1] Scott Aaronson. 2003. Is P versus NP formally independent? Bull. EATCS 81 (2003), 109–136. [2] Barış Aydınlıoğlu and Eric Bach. 2018. Affine relativization: Unifying the algebrization and relativization barriers. ACM Trans. Comput. Theory 10, 1 (2018), 1:1–1:67. DOI:https://doi.org/10.1145/3170704 [3] Martin Löb. 1955. Solution of a problem of Leon Henkin. J. Symbol. Logic 20, 2 (1955), 115–118. Authors’ addresses: B. Aydınlıoğlu and E. Bach, Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI; emails: {baris, bach}@cs.wisc.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Association for Computing Machinery. 1942-3454/2019/04-ART16 $15.00 https://doi.org/10.1145/3317693 ACM Transactions on Computation Theory, Vol. 11, No. 3, Article 16. Publication date: April 2019.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 3, 2019

Keywords: Algebrization

References

  • Is P versus NP formally independent? Bull
    Aaronson, Scott
  • Affine relativization: Unifying the algebrization and relativization barriers
    Aydınlıoğlu, Barış; Bach, Eric
  • Solution of a problem of Leon Henkin
    Löb, Martin