The W Hierarchy

50 %
50 %
Information about The W Hierarchy
Education

Published on March 6, 2014

Author: ASPAK2014

Source: slideshare.net

The W-Hierarchy

A Parametereized Problem

A Parametereized Problem NP-hard for constant values of the parameter “Easy” for small values of the parameter

“Easy” for small values of the parameter

“Easy” for small values of the parameter An O(nk) algorithm exists.

“Easy” for small values of the parameter An O(nk) algorithm exists. Fixed-Parameter Tractable: f(k)poly(n) As hard as solving Clique

“Easy” for small values of the parameter An O(nk) algorithm exists. Polynomial “Stuck” with kernel large instances As hard as solving Clique

To establish membership, reduce to X.

A problem is “hard” for a class if every problem in the class reduces to it.

A problem is “hard” for a class if every problem in the class reduces to it.

A problem is “hard” for a class if every problem in the class reduces to it.

A problem is “hard” for a class if every problem in the class reduces to it.

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance Input A [ND] Turing machine M, an input x, and an integer k.

Short Turing Machine Acceptance Input A [ND] Turing machine M, an input x, and an integer k. Does M accept x in at most k steps? Question

Independent Set Short Turing Machine Acceptance

Independent Set Short Turing Machine Acceptance (qa,happy)

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is an edge.

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is an edge. (qa,happy) —> (QUIT)

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is not an edge. (qa,happy) —> (QUIT)

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is not an edge. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) Read an EOF symbol. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) Read an EOF symbol. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left

Independent Set Short Turing Machine Acceptance (qa,happy) Read a. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left

Independent Set Short Turing Machine Acceptance (qa,happy) Read a. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left (q[move,a],happy) —> (q[read],happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left (q[move,a],happy) —> (q[read],happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left (q[move,a],happy) —> (q[read],happy); move right (q[read],happy) —> (qb,happy); move right

Dominating Set Short Turing Machine Acceptance

Dominating Set Short Turing Machine Acceptance

Short Turing Machine Acceptance Independent Set

Short Turing Machine Acceptance Independent Set

Short Turing Machine Acceptance Independent Set

Short Turing Machine Acceptance Independent Set

A problem is “hard” for a class if every problem in the class reduces to it.

Short Turing Machine Acceptance

Short Turing Machine Acceptance Encode every configuration as a vertex.

Short Turing Machine Acceptance Encode every configuration as a vertex. At step i, the head is at j, and the transition is δ.

Short Turing Machine Acceptance Encode every configuration as a vertex. At step i, the head is at j, and the transition is δ. At step i, the symbol at j is t, and the head is not at j.

[Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

Introducing… CIRCUITS

CIRCUITS

CIRCUITS

Weighted Circuit Satisfiablity

Weighted Circuit Satisfiablity Input A circuit C, and an integer k.

Weighted Circuit Satisfiablity Input A circuit C, and an integer k. Is there an assignment setting EXACTLY k variables to one, that satisfies C? Question

Independent Set Weighted Circuit Satisfiability e b c a t d h f g

Independent Set Weighted Circuit Satisfiability e b c a t d t h f g h

Independent Set Weighted Circuit Satisfiability e b c a t d t h f g h AND

Independent Set Weighted Circuit Satisfiability e b c a t d t h f g h AND

Independent Set Weighted Circuit Satisfiability e a t t h NOT b c d h f g AND

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability Vertices as Input Gates NOT Gates Edges as AND Gates Output Gate [AND]

Dominating Set Weighted Circuit Satisfiability

Dominating Set Weighted Circuit Satisfiability OR Gates

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate Set a Dominating Set to 1 and the rest to 0…

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate Set a Dominating Set to 1 and the rest to 0…

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate Otherwise:

Weighted Circuit Satisfiability Independent Set

Weighted Circuit Satisfiability Independent Set

Weighted Circuit Satisfiability Independent Set

Weighted Circuit Satisfiability Independent Set

The weft of a circuit is the maximum number of large nodes on a path from an input node to the output node. *Nodes with in-degree more than two.

Independent Set Weighted Circuit Satisfiability Vertices as Input Gates NOT Gates Edges as AND Gates Output Gate [AND]

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Weighted Circuit Satisfiability restricted to circuits of weft 1. Independent Set, Clique, etc. W[1]

Weighted Circuit Satisfiability restricted to circuits of weft 2. W[2]

Weighted Circuit Satisfiability restricted to circuits of weft 2. Dominating Set, Set Cover, Hitting Set W[2]

Weighted Circuit Satisfiability restricted to circuits of weft 2. Dominating Set, Set Cover, Hitting Set W[2]

Weighted Circuit Satisfiability restricted to circuits of weft 2. Dominating Set, Set Cover, Hitting Set W[2]

CIRCUITS & SATISFIABILITY (as we know it)

Independent Set Weighted Circuit Satisfiability Vertices as Input Gates NOT Gates Edges as AND Gates Output Gate [AND]

Input Gates NOT Gates AND Gates Output Gate [AND]

(x y) (z x) ··· (z y) Input Gates NOT Gates AND Gates Output Gate [AND]

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

OR Gates AND Gate

(x y a b p q) (z OR Gates AND Gate x r) ··· (z y p q z)

Weighted Circuit Satisfiability restricted to circuits of weft 2.

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

(x y a b p q) (z x r) ··· (z y p q z)

(x y a b p q) (z x r) ··· (z y p q z)

(x y a b p q) (z p x r) ··· (z y p q z)

(x y a b p q) (z p x r) ··· (z y p q z)

Add a comment

Related presentations

Related pages

The W-Hierarchy | springerprofessional.de

We introduce the W-hierarchy of parameterized complexity classes in the tower
Read more

dict.cc Wörterbuch :: hierarchy :: Deutsch-Englisch ...

Englisch-Deutsch-Übersetzung für hierarchy im Online-Wörterbuch dict.cc (Deutschwörterbuch).
Read more

The WordPress Template Hierarchy - a visualization resource

The WordPress Template Hierarchy . Menu WP Hierarchy. is current up to: WordPress 4.6. Latest update: Tuesday June 28, 2016: Udpate stripCount and adjust ...
Read more

Hierarchy | Definition of Hierarchy by Merriam-Webster

The church hierarchy faced resistance to some of their decisions. He was at the bottom of the corporate hierarchy. a rigid hierarchy of social classes.
Read more

The W-Hierarchy - Springer

Based on the syntactic approach to complexity theory laid out in Chap. 4, we introduced the classes W ( [1] ), W ( [2],dots ), of the W-hierarchy by ...
Read more

dict.cc | hierarchy | Wörterbuch Englisch-Deutsch

Übersetzung für hierarchy im Englisch-Deutsch-Wörterbuch dict.cc.
Read more

Descriptive Complexity and the W Hierarchy - researchgate.net

DESCRIPTIVE COMPLEXITY AND THE W HIERARCHY 3 For the completeness notion, Downey and Fellows [DF95] de ned a hierarchy of classes of parameterized languages
Read more

An analysis of the W*-hierarchy - Semantic Scholar

An analysis of the W*-hierarchy. Yijia Chen, Jörg Flum, Martin Grohe; JSYML; 2007; View PDF; Cite; Save; Abstract. We observe that the W *-hierarchy, a ...
Read more

www.mpi-inf.mpg.de

Theory Comput Syst DOI 10.1007/s00224-008-9138-6 W-Hierarchies Defined by Symmetric Gates Michael Fellows ·Jörg Flum ·Danny Hermelin · Moritz Müller ...
Read more

Hierarchie – Wikipedia

Hierarchie, Gruppendynamik und die neue Rolle der Frauen. 5. überarbeitete Auflage. VS, Verlag für Sozialwissenschaften, Wiesbaden 2007, ...
Read more