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

May
15
revised Proving that Unit Intersection is NP-complete
mathjaxed some variables, boldfaced problem names
May
15
revised Proving UNIT INTERSECTION NP-complete
mathjaxed some variables, boldfaced problem names
May
15
answered Proving UNIT INTERSECTION NP-complete
May
15
suggested approved edit on Proving that Unit Intersection is NP-complete
May
15
suggested approved edit on Proving UNIT INTERSECTION NP-complete
May
14
revised Connect 4 - SAT
took another swing at this answer with some details this time around
May
14
answered Proving that Unit Intersection is NP-complete
May
4
comment An easy question about NP-hard
@DavidK I do see your point, but integer programming changes the domain of possible solutions; it isn't simply fixing a variable within the existing domain. So IP is not a restricted version of LP, it's a different problem altogether.
May
2
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?
May
2
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.
May
2
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$.
May
2
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.