*think think* ... if I was just skimming, it might not be obvious that I can solve my FGCOLOR problems with the 3SAT library I have hanging around too. But you could do that, right? ...

Also: \m/ !! Rock, rock on!

(one tiny nit: it's not proved that P != NP yet, so we can't strictly say that FGCOLOR isn't solvable in polytime!)

You're right. Okay, here: "Therefore 3SAT is polynomial time reducible to FGCOLOR. Since 3SAT is NP-complete and FGCOLOR is in NP, FGCOLOR is NP-complete." I hope I don't have to show that FGCOLOR is in NP.

Ooh! Right on. That's a better way to think about it -- if a problem is in NP at all, then it's polytime reducible to any NP-complete problem? That's true, right? ...

I was thinking like "oh, how could I go about reducing it the other way? ..." ... which is much clunkier.

My train of thought was that if it's in NP and it's polynomial-time reducible to an NP-complete problem, then it is also NP-complete.

At least, that's what they done learned me in school.

You do have to show that FGCOLOR is in NP, but to prove that it suffices to point out that you can verify a correct coloring in polynomial (linear!) time.

You have only proved that your problem is *at least as hard* as 3SAT (aka NP-HARD). To prove completeness, you must show that it is no harder, ie that FGCOLOR is in NP. As an example for why this is true, I can prove that I can encode 3SAT as a TQBF problem (very easy, just don't do any forall on any of the variables), but all that means is that TQBF is at least as hard as 3SAT. I can't (currently) figure out how to encode a TQBF problem as a 3SAT problem, and this is kind of expected because Totally Quantified Boolean Formula is PSPACE complete and 3SAT is NP Complete, and we conjecture (but nobody has proven) that NP is a proper subset of PSPACE.

You mean to say that she's proved that her problem is *no harder* than 3SAT, I think.

Nope. That's what she needs to prove. She has proven that a solver for ehr problem could solve 3SAT, but has not proven that a solver for 3SAT could solve her problem. Thus, she has only shown that her problem is no easier than 3SAT. We need to know that 3SAT is no easier than her problem.

I'm reading it backwards, I guess. It looks at a glance as though she's reducing her graph to a 3SAT construction ("a_i is true if..."). That obviously doesn't make sense, though.

Don't mind me, I'm just a poor college dropout.

Yeah, I wrote those badly. I'm actually trying to reduce from 3SAT, not to it. That is, I want to model 3SAT as an FGCOLOR problem. Basically, it sucks and I need to fix it.

Oh crap! I just skimmed your thing, but you are totally right. Fortunately, it looks like your construction only needs to be slightly changed to embed 3SAT in your problem instead of vice-versa. Your intuition about "one vertex per clause" and "one color per truth value" seem (to me) to be right on.

You do have to show that FGCOLOR is in NP, but to prove that it suffices to point out that you can verify a correct coloring in polynomial (linear!) time.

Yeah, I figured there was probably a polynomial time verifier, but I got hung up on silly implementation details of how to represent the different-shaped nodes and so on. I guess it would be linear. You have a graph. A subset of its nodes are square. Looking at each square node and testing if it meets the conditions takes constant time, so O(n) overall.

For the win!

After a few minutes with it today, I'm convinced that it's nonsensical to say things like "give the graph feature so-and-so if a_i is true", because we have to be able to do the reduction without having a satisfying assignment for the formula (and, in fact, without even knowing if we can have a satisfying assignment for the formula). I'm going to play with it some more.

Aha!

You figured this out in the time it took me to compose the below reply. Good jerb!

Sorry to be a downer here, but I'm frankly having a little trouble following your argument.

I agree that you want to (poly-time) reduce 3SAT to FGCOLOR; if you can do this, then solving the latter is tantamount to solving the former, and thus FGCOLOR is NP-hard. (Showing that FGCOLOR is NP is relatively trivial, and while it's necessary to do for a complete proof, I won't bother going into the details here, except to say that a witness for FGCOLOR -- that is, a specific colouring for a funny graph that satisfies the criteria -- can be verified in polynomial time.)

Then, since FGCOLOR is in NP, and (assuming we can show) FGCOLOR is NP-hard, it follows by definition that FGCOLOR is NP-complete, WWWWW.

Great. So far, so good.

However... your reduction (from 3SAT to FGCOLOR) doesn't seem to make a lot of sense to me. Specifically, I'm having trouble with your 3 bullet points. As I understand it, you are trying to construct a funny graph G from φ (which seems to me correct -- if you do it such that solving FGCOLOR on G solves 3SAT on φ, and the reduction is complete). But the way you've written those bullet points, you seem to be doing the construction backwards: a_i is true if <G has such-and-such a property>. Here, φ seems to depend on G? Or are you trying to demonstrate how solving FGCOLOR solves 3SAT... in which case, where is your construction?

Or am I missing something? I'm afraid I rather feel like I am.


I think a more concise way would be to consider what FGGRAPH and 3SAT actually require.

FGGRAPH takes a structure (the graph) containing elements of type A (circle vertices), and type B (square vertices) where each B-element is related to one or more A-elements (via edges) in one of two ways (in or out). The question is whether it is possible to give each A-element one of two values (colours) such that a particular property is satisfied for at least one relation on every B-element (in from red or out to green).

Now, 3SAT takes a structure (the formula) containing elements of type A (variables), and type B (clauses) where each B-element is related to specifically 3 A-elements (via terms) in one of two ways (a variable or a negated variable). The question is whether it is possible to give each A-element one of two values (true or false) such that a particular property is satisfied for at least one relation on every B-element (either a variable is true or a negated variable is false).

Do you see where this is going now? Hopefully the ROT13-ed construction below becomes apparent...

Fb gb pbafgehpg T sebz φ, jr jnag gb znxr gur N-ryrzragf zngpu naq gur O-ryrzragf zngpu. Gung vf, pbafgehpg na N-ryrzrag va T sbe rirel N-ryrzrag va φ, n O-ryrzrag va T sbe rirel O-ryrzrag va φ fhpu gung gur eryngvbaf ner naq n eryngvba (bs gur pbeerpg glcr) orgjrra na N naq O ryrzrag-cnve va T jurarire nal fhpu eryngvba rkvfgf orgjrra gur pbeerfcbaqvat N naq O ryrzrag cnve va φ. Gura fbyivat STPBYBE ba T vf gur fnzr nf fbyivat 3FNG ba φ, naq gur erqhpgvba vf pbzcyrgr.


Juvpu vf gb fnl:
Pbafvqre
    φ = (n₁ ∨ o₁ ∨ p₁) ∧ (n₂ ∨ o₂ ∨ p₂) ∧ ... ∧ (n_x ∨ o_x ∨ p_x)
jurer rnpu n_v, o_v be p_v vf rvgure n inevnoyr k_w (sbe fbzr w) be vgf artngvba ¬k_w.

Gura, sbe rirel inevnoyr k_w, pbafgehpg n pvephyne iregrk (ynory vg w; gur ynoryvat vf whfg sbe gur checbfrf bs pbafgehpgvba naq jba'g or hfrq va fbyivat STPBYBE). Sbe rirel pynhfr v, pbafgehpg n fdhner iregrk (ynory vg v). Vs n_v ercerfragf gur grez k_w, gura pbafgehpg na rqtr sebz fdhner v gb pvepyr w. Vs nv ercerfragf gur grez ¬k_w, gura vafgrnq pbafgehpg na rqtr sebz pvepyr w gb fdhner v.

Naq lbh'er qbar! Gur erfg whfg snyyf bhg.

STPBYBE vf fngvfsvrq vs gurer vf n jnl bs pbybhevat gur pvepyrf fhpu gung rirel fdhner unf ng yrnfg bar bhg-rqtr gb n terra pvepyr, be ng yrnfg bar va-rqtr sebz n erq iregrk. Ohg gung zrnaf gung jr pna nffvta inevnoyr k_w (va φ) gur inyhr gehr vs pvepyr w vf terra, be snyfr vs pvepyr w vf erq. Gura vs STPBYBE vf fngvfsvrq, rirel pynhfr va φ jvyy unir ng yrnfg bar grez ercerfragvat n gehr inevnoyr, be ng yrnfg bar grez ercerfragvat gur artngvba bs n snyfr inevnoyr. JJJJJ.


Bxnl, npghnyyl lbh fgvyy unir gb qrzbafgengr gung gur pbafgehpgvba pna or qbar va cbyl-gvzr, ohg gung'f cerggl gevivny, ernyyl.

> gura vafgrnq pbafgehpg na rqtr sebz pvepyr w gb fdhner v.

Neetu. Ercrng cebprff sbe o_v naq p_v, boivbhfyl. V'z trggvat fybccl.


> fhpu gung gur eryngvbaf ner

Naq fgevxr gung grkg. Vg fubhyq unir ernq:

"...n O-ryrzrag va T sbe rirel O-ryrzrag va φ naq n eryngvba (bs gur pbeerpg glcr) orgjrra na N naq O ryrzrag-cnve va T jurarire..."

Furrfu.

> Which goes to show that you should always reduce from 3SAT. Always.

Hmm. This is dangerous. While 3SAT is very often the best choice, there are definitely problems out there which can be tackled much much easier by choosing other reductions.

I like subgraph-isomorphism and subset-sum, myself.

Oh, definitely. I'm just poking fun at people who make a religion out of always reducing from 3SAT, even when there's an easier choice.

(But I do like 3SAT a lot.)