Complete (complexity)
id:
complete-complexity-315-3510961
title:
Complete (complexity)
text:
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" problems in the complexity class. More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction from any problem in C to p. If a problem is both hard for the class and a member of the class, it is complete for that class. A problem that is complete for a class C is said to be C-complete,
brand slug:
wiki
category slug:
encyclopedia
description:
Notion of the "hardest" or "most general" problem in a complexity class
original url:
https://en.wikipedia.org/wiki/Complete_(complexity)
date created:
date modified:
2022-04-18T18:30:42Z
main entity:
{"identifier":"Q2532728","url":"https://www.wikidata.org/entity/Q2532728"}
image:
fields total:
13
integrity:
14