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