Self-witnessing polynomial-time complexity and prime factorization
type: Item
instance of: scholarly article
title: Self-witnessing polynomial-time complexity and prime factorization
zbMATH Open document ID: 0756.11042
DOI: 10.1007/BF00141967
author: Michael R. Fellows
author: Neal Koblitz
published in: Designs, Codes and Cryptography
publication date: 1993-01-16T00:00:00Z
review text: A computational problem \(X\) is called \(P\)-time self-witnessing, if ``the idealized collective mathematician'' possesses a theorem of the form: \(A\) is an algorithm such that if there exists any algorithm \(B\) and polynomial \(q\) such that \(B\) solves \(X\) in time bounded by \(q\), then there exists a polynomial \(q'\) such that \(A\) solves \(X\) in time bounded by \(q'\). Another, more informal definition is: If there exists a polynomial-time algorithm for \(X\) then we constructively know one. After introducing this new concept it is proved that the problems of computing a prime factorization and of the \(k\)-fold planar cover search are \(P\)- time self-witnessing. The paper concludes with the open problem: Can we prove some familiar \(NP\)-hard problem to be \(P\)-time self-witnessing?
reviewed by: Attila Pethő
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 95039
zbMATH Keywords: time self-witnessing
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: prime factorization
zbMATH Keywords: planar cover search
MaRDI profile type: Publication
cites work: Q3679172
cites work: Q5514677
cites work: The NP-completeness column: An ongoing guide
cites work: Q4071737
cites work: Riemann's hypothesis and tests for primality
cites work: A course in constructive algebra
cites work: Every Prime Has a Succinct Certificate
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Q4001322
Wikidata QID: Q57360143
full work available at URL: https://doi.org/10.1007/bf00141967
OpenAlex ID: W2106380698
description: scientific article; zbMATH DE number 95039