Comments: 
*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 NPcomplete and FGCOLOR is in NP, FGCOLOR is NPcomplete." I hope I don't have to show that FGCOLOR is in NP.
 From: oniugnip 20080826 04:02 am (UTC)
Re: "God all these RULES!"  (Link)

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 NPcomplete 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 polynomialtime reducible to an NPcomplete problem, then it is also NPcomplete.
At least, that's what they done learned me in school.
 From: pmb 20080826 02:29 pm (UTC)
Re: "God all these RULES!"  (Link)

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 NPHARD). 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.
 From: conform 20080826 03:00 pm (UTC)
Re: "God all these RULES!"  (Link)

You mean to say that she's proved that her problem is *no harder* than 3SAT, I think.
 From: pmb 20080826 03:43 pm (UTC)
Re: "God all these RULES!"  (Link)

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.
 From: conform 20080826 04:24 pm (UTC)
Re: "God all these RULES!"  (Link)

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.
 From: pmb 20080826 05:37 pm (UTC)
Re: "God all these RULES!"  (Link)

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 viceversa. 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 differentshaped 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.
 From: pmb 20080826 05:32 pm (UTC)
Re: "God all these RULES!"  (Link)

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 soandso 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.
From: (Anonymous) 20080827 09:48 am (UTC)
 (Link)

Aha!
You figured this out in the time it took me to compose the below reply. Good jerb!
From: (Anonymous) 20080827 09:45 am (UTC)
 (Link)

Sorry to be a downer here, but I'm frankly having a little trouble following your argument.
I agree that you want to (polytime) reduce 3SAT to FGCOLOR; if you can do this, then solving the latter is tantamount to solving the former, and thus FGCOLOR is NPhard. (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 NPhard, it follows by definition that FGCOLOR is NPcomplete, 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 suchandsuch 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 Belement is related to one or more Aelements (via edges) in one of two ways (in or out). The question is whether it is possible to give each Aelement one of two values (colours) such that a particular property is satisfied for at least one relation on every Belement (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 Belement is related to specifically 3 Aelements (via terms) in one of two ways (a variable or a negated variable). The question is whether it is possible to give each Aelement one of two values (true or false) such that a particular property is satisfied for at least one relation on every Belement (either a variable is true or a negated variable is false).
Do you see where this is going now? Hopefully the ROT13ed construction below becomes apparent...
From: (Anonymous) 20080827 09:46 am (UTC)
 (Link)

Fb gb pbafgehpg T sebz φ, jr jnag gb znxr gur Nryrzragf zngpu naq gur Oryrzragf zngpu. Gung vf, pbafgehpg na Nryrzrag va T sbe rirel Nryrzrag va φ, n Oryrzrag va T sbe rirel Oryrzrag va φ fhpu gung gur eryngvbaf ner naq n eryngvba (bs gur pbeerpg glcr) orgjrra na N naq O ryrzragcnve 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_{1} ∨ o_{1} ∨ p_{1}) ∧ (n_{2} ∨ o_{2} ∨ p_{2}) ∧ ... ∧ (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 bhgrqtr gb n terra pvepyr, be ng yrnfg bar varqtr 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 cbylgvzr, ohg gung'f cerggl gevivny, ernyyl.
From: (Anonymous) 20080827 10:35 am (UTC)
 (Link)

> 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 Oryrzrag va T sbe rirel Oryrzrag va φ naq n eryngvba (bs gur pbeerpg glcr) orgjrra na N naq O ryrzragcnve va T jurarire..."
Furrfu.
From: (Anonymous) 20080827 09:51 am (UTC)
 (Link)

> 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 subgraphisomorphism and subsetsum, 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.)  