220:
141:
240:
185:
165:
451:
52:. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.
813:
405:
367:
444:
853:
20:
35:
848:
437:
829:
636:
83:
818:
71:
can have any output that can be computed in polynomial time. For example, adding two numbers is an
772:
767:
762:
310:
Because a machine that uses logarithmic space has at most polynomially many configurations,
190:
111:
757:
377:
257:
is the set of binary relations for which there is a polynomial time algorithm that, given
8:
225:
170:
150:
777:
401:
363:
316:, the set of function problems which can be calculated in logspace, is contained in
741:
631:
563:
553:
460:
373:
287:
253:
43:
31:
24:
736:
726:
683:
673:
666:
656:
646:
604:
599:
594:
558:
536:
531:
526:
514:
509:
504:
499:
359:
312:
106:
39:
424:
731:
619:
541:
494:
333:
329:
328:; this is analogous to the problem of determining whether the decision classes
48:
147:
if and only if there is a deterministic polynomial time algorithm that, given
842:
609:
519:
391:
87:
395:
721:
546:
716:
429:
711:
706:
651:
474:
358:. Algorithms and Computation in Mathematics. Vol. 7. Berlin:
701:
808:
803:
678:
661:
397:
Automata, computability and complexity: theory and applications
82:
Polynomial-time function problems are fundamental in defining
798:
793:
614:
626:
484:
641:
573:
568:
489:
479:
356:
Completeness and reduction in algebraic complexity theory
228:
193:
173:
153:
114:
75:
problem, while determining if their sum is odd is in
394:(2008). "28.10 "The problem classes FP and FNP"".
234:
214:
179:
159:
135:
840:
86:, which are used in turn to define the class of
67:have one-bit, yes/no answers, while problems in
445:
246:
42:. It is the function problem version of the
452:
438:
353:
841:
459:
433:
390:
93:
400:. Prentice Hall. pp. 689–694.
13:
14:
865:
814:Probabilistically checkable proof
418:
101:is formally defined as follows:
222:holds, or signals that no such
21:computational complexity theory
384:
347:
209:
197:
130:
118:
1:
340:
36:deterministic Turing machine
7:
10:
870:
830:List of complexity classes
320:. It is not known whether
247:Related complexity classes
84:polynomial-time reductions
827:
786:
750:
694:
587:
467:
354:Bürgisser, Peter (2000).
819:Interactive proof system
34:that can be solved by a
55:The difference between
854:Functions and mappings
773:Arithmetical hierarchy
285:is closely related to
236:
216:
215:{\displaystyle P(x,y)}
181:
161:
137:
136:{\displaystyle P(x,y)}
768:Grzegorczyk hierarchy
763:Exponential hierarchy
695:Considered infeasible
281:are closely related,
237:
217:
182:
162:
138:
758:Polynomial hierarchy
588:Suspected infeasible
226:
191:
171:
167:, either finds some
151:
112:
63:is that problems in
787:Families of classes
468:Considered feasible
265:, checks whether P(
849:Complexity classes
461:Complexity classes
425:Complexity Zoo: FP
273:) holds. Just as
232:
212:
177:
157:
133:
836:
835:
778:Boolean hierarchy
751:Class hierarchies
235:{\displaystyle y}
180:{\displaystyle y}
160:{\displaystyle x}
94:Formal definition
32:function problems
861:
454:
447:
440:
431:
430:
412:
411:
388:
382:
381:
351:
241:
239:
238:
233:
221:
219:
218:
213:
186:
184:
183:
178:
166:
164:
163:
158:
142:
140:
139:
134:
44:decision problem
25:complexity class
16:Complexity class
869:
868:
864:
863:
862:
860:
859:
858:
839:
838:
837:
832:
823:
782:
746:
690:
684:PSPACE-complete
583:
463:
458:
421:
416:
415:
408:
389:
385:
370:
360:Springer-Verlag
352:
348:
343:
299:if and only if
249:
227:
224:
223:
192:
189:
188:
172:
169:
168:
152:
149:
148:
113:
110:
109:
107:binary relation
96:
40:polynomial time
17:
12:
11:
5:
867:
857:
856:
851:
834:
833:
828:
825:
824:
822:
821:
816:
811:
806:
801:
796:
790:
788:
784:
783:
781:
780:
775:
770:
765:
760:
754:
752:
748:
747:
745:
744:
739:
734:
729:
724:
719:
714:
709:
704:
698:
696:
692:
691:
689:
688:
687:
686:
676:
671:
670:
669:
659:
654:
649:
644:
639:
634:
629:
624:
623:
622:
620:co-NP-complete
617:
612:
607:
597:
591:
589:
585:
584:
582:
581:
576:
571:
566:
561:
556:
551:
550:
549:
539:
534:
529:
524:
523:
522:
512:
507:
502:
497:
492:
487:
482:
477:
471:
469:
465:
464:
457:
456:
449:
442:
434:
428:
427:
420:
419:External links
417:
414:
413:
406:
383:
368:
362:. p. 66.
345:
344:
342:
339:
338:
337:
308:
248:
245:
244:
243:
231:
211:
208:
205:
202:
199:
196:
176:
156:
132:
129:
126:
123:
120:
117:
95:
92:
30:is the set of
15:
9:
6:
4:
3:
2:
866:
855:
852:
850:
847:
846:
844:
831:
826:
820:
817:
815:
812:
810:
807:
805:
802:
800:
797:
795:
792:
791:
789:
785:
779:
776:
774:
771:
769:
766:
764:
761:
759:
756:
755:
753:
749:
743:
740:
738:
735:
733:
730:
728:
725:
723:
720:
718:
715:
713:
710:
708:
705:
703:
700:
699:
697:
693:
685:
682:
681:
680:
677:
675:
672:
668:
665:
664:
663:
660:
658:
655:
653:
650:
648:
645:
643:
640:
638:
635:
633:
630:
628:
625:
621:
618:
616:
613:
611:
608:
606:
603:
602:
601:
598:
596:
593:
592:
590:
586:
580:
577:
575:
572:
570:
567:
565:
562:
560:
557:
555:
552:
548:
545:
544:
543:
540:
538:
535:
533:
530:
528:
525:
521:
518:
517:
516:
513:
511:
508:
506:
503:
501:
498:
496:
493:
491:
488:
486:
483:
481:
478:
476:
473:
472:
470:
466:
462:
455:
450:
448:
443:
441:
436:
435:
432:
426:
423:
422:
409:
407:0-13-228806-0
403:
399:
398:
393:
387:
379:
375:
371:
369:3-540-66752-0
365:
361:
357:
350:
346:
335:
331:
327:
323:
319:
315:
314:
309:
306:
302:
298:
294:
290:
289:
284:
280:
276:
272:
268:
264:
260:
256:
255:
251:
250:
229:
206:
203:
200:
194:
174:
154:
146:
127:
124:
121:
115:
108:
104:
103:
102:
100:
91:
89:
85:
80:
78:
74:
70:
66:
62:
58:
53:
51:
50:
45:
41:
37:
33:
29:
26:
22:
578:
396:
392:Rich, Elaine
386:
355:
349:
325:
321:
317:
311:
304:
300:
296:
292:
286:
282:
278:
274:
270:
266:
262:
258:
252:
144:
98:
97:
81:
76:
72:
68:
64:
60:
56:
54:
47:
27:
18:
667:#P-complete
605:NP-complete
520:NL-complete
88:NP-complete
843:Categories
722:ELEMENTARY
547:P-complete
378:0948.68082
341:References
336:are equal.
187:such that
90:problems.
717:2-EXPTIME
712:EXPSPACE
707:NEXPTIME
475:DLOGTIME
702:EXPTIME
610:NP-hard
242:exists.
809:NSPACE
804:DSPACE
679:PSPACE
404:
376:
366:
143:is in
46:class
23:, the
799:NTIME
794:DTIME
615:co-NP
627:TFNP
402:ISBN
364:ISBN
332:and
277:and
261:and
59:and
742:ALL
642:QMA
632:FNP
574:APX
569:BQP
564:BPP
554:ZPP
485:ACC
374:Zbl
297:FNP
288:FNP
254:FNP
38:in
19:In
845::
737:RE
727:PR
674:IP
662:#P
657:PP
652:⊕P
647:PH
637:AM
600:NP
595:UP
579:FP
559:RP
537:CC
532:SC
527:NC
515:NL
510:FL
505:RL
500:SL
490:TC
480:AC
372:.
326:FP
324:=
322:FL
318:FP
313:FL
305:NP
303:=
295:=
293:FP
291:.
283:NP
279:FP
145:FP
105:A
99:FP
79:.
73:FP
69:FP
57:FP
28:FP
732:R
542:P
495:L
453:e
446:t
439:v
410:.
380:.
334:L
330:P
307:.
301:P
275:P
271:y
269:,
267:x
263:y
259:x
230:y
210:)
207:y
204:,
201:x
198:(
195:P
175:y
155:x
131:)
128:y
125:,
122:x
119:(
116:P
77:P
65:P
61:P
49:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.