?

Log in

No account? Create an account
My rhymes are so phat. - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

My rhymes are so phat. [Aug. 25th, 2008|09:06 pm]
Lindsey Kuper
[Tags|]

Last problem on the 2006 foundations qual:

Let a "funny graph" be a finite directed-graph where each vertex is either "square" or "circular" (but not both), and each edge is between a square vertex and a circular vertex (in either order). Prove that the following problem is NP-complete.

  • Given a funny graph, is there a way to color the circular vertices red or green, so that every square vertex either has an out-edge to a green vertex, or an in-edge from a red vertex.

My proof:

Let FGCOLOR = {⟨G⟩| G is a funny graph that is colorable so that every square vertex either has an out-edge to a green vertex or an in-edge from a red vertex }. We give a polynomial time reduction from 3SAT to FGCOLOR.

The reduction maps a Boolean formula φ to a graph G. Let φ be a formula with k clauses such as

&phi = (a1b1c1) ∧ (a2b2c2) ∧ … ∧ (akbkck).

For each clause (aibici) in φ, let there be a square vertex s in G such that

  • ai is true if s has an out-edge to a green vertex;
  • bi is true if s has an in-edge from a red vertex;
  • ci is true if s has both.

Then all clauses (aibici) in φ will be true iff all square vertices in G satisfy the definition of FGCOLOR. Therefore we can model 3SAT as an FGCOLOR problem. But 3SAT is NP-complete, therefore FGCOLOR must not be solvable in polynomial time. Therefore FGCOLOR is NP-complete.

Ideally, I think I should be more explicit about proving both directions of that iff. But I also think my construction works, and I thought of it all by myself! (My first idea was to reduce from the 3-coloring problem, but that didn't work for me. Which goes to show that you should always reduce from 3SAT. Always.)

I guess this might not be so special, really. But I'm excited, because it's been over four years since I've tried to do an NP-completeness proof. And I can do it! I can do it!

LinkReply

Comments:
[User Picture]From: oniugnip
2008-08-26 03:20 am (UTC)
*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!)
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-08-26 03:49 am (UTC)

"God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: oniugnip
2008-08-26 04:02 am (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2008-08-26 11:38 am (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2008-08-26 02:29 pm (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: conform
2008-08-26 03:00 pm (UTC)

Re: "God all these RULES!"

You mean to say that she's proved that her problem is *no harder* than 3SAT, I think.
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2008-08-26 03:43 pm (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: conform
2008-08-26 04:24 pm (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2008-08-26 04:52 pm (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2008-08-26 05:37 pm (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2008-08-26 04:57 pm (UTC)

Re: "God all these RULES!"

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.
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2008-08-26 05:32 pm (UTC)

Re: "God all these RULES!"

For the win!
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2008-08-26 12:12 pm (UTC)
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 ai 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.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-08-27 09:48 am (UTC)
Aha!

You figured this out in the time it took me to compose the below reply. Good jerb!
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-08-27 09:45 am (UTC)
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: ai 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...
(Reply) (Thread)
From: (Anonymous)
2008-08-27 09:46 am (UTC)
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
    φ = (n1 ∨ o1 ∨ p1) ∧ (n2 ∨ o2 ∨ p2) ∧ ... ∧ (nx ∨ ox ∨ px)
jurer rnpu nv, ov be pv vf rvgure n inevnoyr kw (sbe fbzr w) be vgf artngvba ¬kw.

Gura, sbe rirel inevnoyr kw, 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 nv ercerfragf gur grez kw, gura pbafgehpg na rqtr sebz fdhner v gb pvepyr w. Vs nv ercerfragf gur grez ¬kw, 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 kw (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.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-08-27 10:35 am (UTC)
> gura vafgrnq pbafgehpg na rqtr sebz pvepyr w gb fdhner v.

Neetu. Ercrng cebprff sbe ov naq pv, 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.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-08-27 09:51 am (UTC)
> 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.
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-08-27 05:54 pm (UTC)
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.)
(Reply) (Parent) (Thread)