Opis

• Tytuł:
  Proof Compression and NP Versus PSPACE II: Addendum
• Twórca:
  Gordeev, Lew;
  Haeusler, Edward Hermann
• Współtwórca:
  Gordeev, Lew - University of Tübingen, Department of Computer Science, Nedlitzer Str. 4a, 14612 Falkensee;
  Haeusler, Edward Hermann - Pontificia Universidade Católica do Rio de Janeiro – RJ, Department of Informatics, Rua Marques de São Vicente, 224, Gávea, Rio de Janeiro, Brazil;
  Gordeev, Lew - lew.gordeew@uni-tuebingen.de;
  Haeusler, Edward Hermann - hermann@inf.puc-rio.br
• Opis:
  In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic (HSC) with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction (ND). In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea (due to the second author) is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE.
• Dostępność obiektu:
  Dostęp otwarty
• Prawa: https://creativecommons.org/licenses/by-nc-nd/4.0
• Data:
  2022.08.25;
  2022.01.07
• Typ:
  Other
• Język:
  angielski
• Format:
  application/pdf
• Wydawca:
  Wydawnictwo Uniwersytetu Łódzkiego
• Relacja:
  Bulletin of the Section of Logic;2;
  51
• Temat i słowa kluczowe:
  graph theory;
  natural deduction;
  computational complexity
• Identyfikator:
  0138-0680;
  http://hdl.handle.net/11089/42924 ;
  2449-836X;
  10.18778/0138-0680.2022.01
• Dostawca danych:
  Repozytorium Uniwersytetu Łódzkiego
• Czy mogę z tego obiektu skorzystać?:
  sprawdź warunki licencji
• Rodzaj zawartości:
  pozostałe