Reputation
524
Top tag
Next privilege 1,000 Rep.
Create tags
Badges
1 4 12
Impact
~6k people reached

1d
comment Is showing a graph is non-Hamiltonian NP-Complete?
Showing that NOT-HAMCYCLE is NP-hard is a reasonable undergrad CS exercise. Showing that it is NP-complete would upend theoretical computer science. Are you sure you're not being asked to demonstrate the former?
1d
comment Is showing a graph is non-Hamiltonian NP-Complete?
You'd need a polynomial-time deterministic verifier for (is-not-Hamiltonian), not just a deterministic verifier, to prove (is-not-Hamiltonian) is in NP. This (NP = coNP) would flip the wigs of most theoreticians as much as if P turned out to be equivalent to NP. Tough get for a class assignment, which this question clearly is.
1d
comment An easy question about NP-hard
This would be convincing with a real counterexample, rather than supposing without proof $B_c$ is NP-hard, because on the face of it $B_c$ looks no harder to optimize than $A$.
2d
answered An easy question about NP-hard
Apr
18
comment P vs NP and Countable vs Uncountable Decision Space
Mahaney's Theorem might be the insight that you're struggling toward, otherwise this question makes no sense to me.
Mar
19
answered P vs NP - examples of P and NP
Mar
10
revised “Job-scheduling” problem that minimizes the number of machines
added links for obscure terms
Feb
17
revised some Graph and NP Theory Problems
P=NP is not a known corollary of an NP-complete problem being shown to be in co-NP, so I've corrected the statement to what was probably intended.
Dec
15
revised Check Whether A Boolean Formula Has One Satisfying Assignment
added 3 characters in body
Nov
26
revised Proof of: if L is in NP then its complement is coNP-Complete
changed title to match claim in question
Nov
26
suggested approved edit on Proof of: if L is in NP then its complement is coNP-Complete
Nov
14
comment Using up letters on a refrigerator is NP-complete
The duplicates can be treated as distinct entities as far as set intersection and union are concerned. It's still the same problem.
Nov
14
revised Using up letters on a refrigerator is NP-complete
showed how EXACT COVER maps directly to the poster's problem, linked to Karp's 21 problems on Wikipedia
Nov
14
answered Using up letters on a refrigerator is NP-complete
Nov
13
revised Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover?
NP-complete -> NP-hard; punctuation and spelling
Nov
13
suggested approved edit on Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover?
Oct
18
revised Why do we stop at exponentiation stage in arithmetic of natural numbers?
Used > to quote the question instead of indentation. If you display the page with large fonts, as I do because of my visual impairment, the indented quotation is displayed with a horizontal scrollbar instead of wrapping to the next line. The change wraps the text and gets rid of the scrollbar.
Oct
18
suggested approved edit on Why do we stop at exponentiation stage in arithmetic of natural numbers?
Oct
17
suggested rejected edit on Why do we stop at exponentiation stage in arithmetic of natural numbers?
Sep
24
awarded  Autobiographer