Reputation
676
Top tag
Next privilege 1,000 Rep.
Create new tags
Badges
1 5 12
Newest
 Yearling
Impact
~8k people reached

Jul
23
revised Must an algorithm that decides a problem in NP also produce a solution?
phrasing
Jul
23
answered Must an algorithm that decides a problem in NP also produce a solution?
Jul
7
awarded  Yearling
Jul
7
answered Is it known whether a hypothetical P-time NP-complete decision procedure has to find a specific solution to the given constraint satisfaction problem?
Jul
7
answered Why doesn't the decision problem for Presburger arithmetic demonstrate that $\mathsf{P} \neq \mathsf{NP}$
Jun
23
comment Reorder adjacency matrices of regular graphs so they are the same
Two questions: How is the matrix E created? What definition of permutation are you using? If two strings equal length strings consisting of zeroes and ones only have the same number of ones in them, then the strings are permutable to each other under the definition of permutation I'm familiar with.
May
31
answered Is bipartite maximal matching an NP Hard or NP Complete or neither?
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.