Editing Function problem (section)

== Self-reducibility ==
Observe that the problem '''FSAT''' introduced above can be solved using only polynomially many calls to a subroutine which decides the '''SAT''' problem: An algorithm can first ask whether the formula <math>\varphi</math> is satisfiable. After that the algorithm can fix variable <math>x_1</math> to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps <math>x_1</math> fixed to TRUE and continues to fix <math>x_2</math>, otherwise it decides that <math>x_1</math> has to be FALSE and continues. Thus, '''FSAT''' is solvable in polynomial time using an [[Oracle machine|oracle]] deciding '''SAT'''. In general, a problem in '''NP''' is called ''self-reducible'' if its function variant can be solved in polynomial time using an oracle deciding the original problem. Every '''[[NP-complete]]''' problem is self-reducible. It is conjectured {{By whom|date=February 2020}} that the [[integer factorization problem]] is not self-reducible, because deciding whether an integer is prime is in '''P''' (easy),<ref name="AKS">{{cite journal |first1=Manindra |last1=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |title=PRIMES is in P |journal=[[Annals of Mathematics]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free }}</ref> while the integer factorization problem is believed to be hard for a classical computer.
There are several (slightly different) notions of self-reducibility.<ref>{{cite journal |first= K.|last= Ko|title= On self-reducibility and weak P-selectivity|journal= Journal of Computer and System Sciences|volume= 26|issue=2|pages=209–221|year=1983|doi= 10.1016/0022-0000(83)90013-2}}</ref><ref>{{cite journal |first= C.|last=Schnorr|title=Optimal algorithms for self-reducible problems|journal=In S. Michaelson and R. Milner, Editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming|pages=322–337|year=1976}}</ref><ref>{{cite journal |first=A.|last=Selman|title=Natural self-reducible sets|journal=SIAM Journal on Computing|volume=  17|issue=5|pages=989–996|year=1988|doi=10.1137/0217062 }}</ref>