Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP (Q293222): Difference between revisions

@@ Property / cites work @@
+It is hard to know when greedy is good for finding independent sets
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Greed is good
@@ Property / cites work: Greed is good / rank @@
+Normal rank
@@ Property / cites work @@
+Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
+Normal rank
@@ Property / cites work @@
+The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+The difference and truth-table hierarchies for NP
@@ Property / cites work: The difference and truth-table hierarchies for NP / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of facets (and some facets of complexity)
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Well-covered claw-free graphs
@@ Property / cites work: Well-covered claw-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+More complicated questions about maxima and minima, and some closures of NP
+Normal rank
@@ Property / cites work @@
+Bounded Query Classes
@@ Property / cites work: Bounded Query Classes / rank @@
+Normal rank