25:
217:
Generally, complexity classes that have a recursive enumeration have known complete problems, whereas classes that lack a recursive enumeration have none. For example,
210:
Normally, it is assumed that the reduction in question does not have higher computational complexity than the class itself. Therefore, it may be said that if a
311:
89:
61:
42:
289:
68:
195:, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class
108:
75:
122:
57:
46:
137:
if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class.
236:
There are classes without complete problems. For example, Sipser showed that there is a language
214:
problem has a "computationally easy" solution, then all problems in "C" have an "easy" solution.
82:
35:
153:
126:
8:
285:
277:
230:
226:
134:
218:
272:
Sipser, Michael (1982). "On relativization and the existence of complete sets".
249:
305:
192:
281:
16:
Notion of the "hardest" or "most general" problem in a complexity class
276:. Lecture Notes in Computer Science. Vol. 140. pp. 523–531.
191:. The first complete class to be defined and the most well known is
156:
if there exists a reduction (of the given type) from any problem in
24:
204:
222:
49:. Unsourced material may be challenged and removed.
303:
168:for the class and a member of the class, it is
183:, and the class of all problems complete for
172:for that class (for that type of reduction).
233:all have known natural complete problems.
109:Learn how and when to remove this message
175:A problem that is complete for a class
304:
271:
47:adding citations to reliable sources
18:
274:Automata, Languages and Programming
13:
14:
323:
23:
312:Computational complexity theory
123:computational complexity theory
34:needs additional citations for
265:
1:
258:
255:) has no complete problems.
7:
10:
328:
58:"Complete" complexity
140:More formally, a problem
164:. If a problem is both
148:for a complexity class
152:under a given type of
127:computational problem
43:improve this article
282:10.1007/BFb0012797
291:978-3-540-11576-2
119:
118:
111:
93:
319:
296:
295:
269:
135:complexity class
114:
107:
103:
100:
94:
92:
51:
27:
19:
327:
326:
322:
321:
320:
318:
317:
316:
302:
301:
300:
299:
292:
270:
266:
261:
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
325:
315:
314:
298:
297:
290:
263:
262:
260:
257:
179:is said to be
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
324:
313:
310:
309:
307:
293:
287:
283:
279:
275:
268:
264:
256:
254:
251:
247:
243:
239:
234:
232:
228:
224:
220:
215:
213:
208:
206:
202:
198:
194:
190:
186:
182:
178:
173:
171:
167:
163:
159:
155:
151:
147:
143:
138:
136:
132:
128:
124:
113:
110:
102:
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
273:
267:
252:
245:
241:
237:
235:
216:
211:
209:
200:
196:
188:
184:
180:
176:
174:
169:
165:
161:
157:
149:
145:
141:
139:
130:
120:
105:
99:October 2008
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
193:NP-complete
187:is denoted
259:References
240:such that
212:C-complete
199:is called
189:C-complete
181:C-complete
144:is called
69:newspapers
154:reduction
306:Category
170:complete
131:complete
205:NP-hard
203:, e.g.
83:scholar
288:
250:oracle
201:C-hard
133:for a
85:
78:
71:
64:
56:
248:with
223:co-NP
90:JSTOR
76:books
286:ISBN
166:hard
146:hard
125:, a
62:news
278:doi
246:BPP
242:BPP
231:PPA
227:PLS
160:to
129:is
121:In
45:by
308::
284:.
229:,
225:,
221:,
219:NP
207:.
294:.
280::
253:M
244:(
238:M
197:C
185:C
177:C
162:p
158:C
150:C
142:p
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
