Self-witnessing polynomial-time complexity and prime factorization (Q1200292)

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?