On equivalence between polynomial constructivity of Markov's principle and \(P=NP\)

zbMath0845.03018MaRDI QIDQ1920039

Vladimir Yu. Sazonov

Publication date: 19 August 1996

Published in: Siberian Advances in Mathematics (Search for Journal in Brave)

zbMATH Keywords

intuitionistic logicMarkov principlepolynomial computabilityconstructive selectionconstructivity of a formal theory

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Metamathematics of constructive systems (03F50)

Related Items (1)

\(\Delta\)-languages for sets and LOGSPACE computable graph transformers

This page was built for publication: On equivalence between polynomial constructivity of Markov's principle and \(P=NP\)