Self-witnessing polynomial-time complexity and prime factorization (Q1200292): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3679172 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5514677 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The NP-completeness column: An ongoing guide / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4071737 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Riemann's hypothesis and tests for primality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A course in constructive algebra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Every Prime Has a Succinct Certificate / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. XIII: The disjoint paths problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4001322 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q57360143 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf00141967 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2106380698 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:39, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Self-witnessing polynomial-time complexity and prime factorization |
scientific article |
Statements
Self-witnessing polynomial-time complexity and prime factorization (English)
0 references
16 January 1993
0 references
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?
0 references
time self-witnessing
0 references
polynomial-time algorithm
0 references
prime factorization
0 references
planar cover search
0 references