Kyle Jones
Reputation
524
Top tag
Next privilege 1,000 Rep.
Create tags
 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 Apr18 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. Mar19 answered P vs NP - examples of P and NP Mar10 revised “Job-scheduling” problem that minimizes the number of machines added links for obscure terms Feb17 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. Dec15 revised Check Whether A Boolean Formula Has One Satisfying Assignment added 3 characters in body Nov26 revised Proof of: if L is in NP then its complement is coNP-Complete changed title to match claim in question Nov26 suggested approved edit on Proof of: if L is in NP then its complement is coNP-Complete Nov14 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. Nov14 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 Nov14 answered Using up letters on a refrigerator is NP-complete Nov13 revised Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover? NP-complete -> NP-hard; punctuation and spelling Nov13 suggested approved edit on Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover? Oct18 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. Oct18 suggested approved edit on Why do we stop at exponentiation stage in arithmetic of natural numbers? Oct17 suggested rejected edit on Why do we stop at exponentiation stage in arithmetic of natural numbers? Sep24 awarded Autobiographer