Craig Holman's Blog Jabberwocky

Constraint and Consequence



	Craig Holman Research Jabberwocky Quotations Contact

	Home > Jabberwocky Previous Next


	Jabberwocky for May 31, 2008

What is it?

Next in thread

Applet displaying a beautiful rotating plot of four metrics on 2000 Boolean expressions

My doctoral research involved boolean expressions, and one of the questions I was investigating involved predictive metrics.

I found that a metric that I called 'degree of coincidence', based upon an aspect of the structure of the expression, was a great predictor for whether expressions were tautologies or contradictions.

The Java applet (hopefully) running above displays four pieces of information about several hundred randomly generated boolean expressions.

The color of each dot is the expression's logical class: tautologies, contradictions, and expressions that are both satisfiable and falsifiable.

This is a static view of similar data:

In this view, the horizontal axis is the log₁₀ of the number of clauses in the Conjunctive Normal Form (CNF) equivalent of the expression and the vertical axis is the log₁₀ of the number of clauses in the Disjunctive Normal Form (DNF) equivalent of the expression.

Gorgeous.

The third spatial dimension, projecting out from the screen for the static view, is the Degree of Coincidence for the expression. I'll define this metric much later when I start to present some of my work on boolean expressions.

The important thing to note is how well the Degree of Coincidence separates tautologies from contradictions.

For fun: If you click on the left side of the spinning cluster, it will slow down; if you click on the right side of the spinning clust, it will speed up. Repeat.

This is one of my favorite things.

Next in thread

Search Approach to the k-Clique Exists problem - Introduction to the Text

First in thread Previous in thread

The Text

We can reduce D by removing a directed edge (X, Y) when nodes X and Y can not be in a k-clique together, and by removing node X when X can not be in any k-clique. As we are trying to reduce the search space implicit in D, however, we can use something more refined that allows us to track whether two nodes can occupy two particular adjacent positions in a search sequence of D.

One representation of the search space that facilitates reduction I call the 'text' of the graph. The text of G is a two-dimensional grid of cells, N cells high and K cells wide. The rows of the text are numbered 0 through N-1 and correspond to the nodes of the graph. The columns of the text are numbered 0 through K-1 and correspond to the positions in a search sequence.

Each cell has the following properties:

Row, which is the label of a node of D and is in the range [0 .. N-1].

Column, which is the position in a search sequence of D and is in the range [0 .. K-1].

A State, {Possible, Impossible}, which indicates whether the node Row can possibly occur in position Cell of a valid search sequence of D.

A set of node labels named LocalAAS, or local augmented adjacency set, which is initially set to AAS(Row)

A set of node labels named DownNodes, which is initially set to AAS(Row) intersect Range(0, Row-1), if Column > 0, or to {}, otherwise.

A set of node labels named UpNodes, which is initially set to AAS(Row) intersect Range(0, Row+1), if Column < K-1, or to {}, otherwise.

A cell-edge exists between cells (Row1, Column1) and (Row2, Column1+1) iff a transition from node Row1 to node Row2 has not been proven to be impossible when node Row1 is in position Column1 in a search sequence.

A node is a singularity if it is the only node that can only occur in a postion in a search sequence.

Let Singularities denote the set of singularities of D.

Reduction of the text

The work of reducing the text has been split into three stages:

Initialization of the text, which uses two structural rules to give the initial text its characteristic shape

Propagation of constraints, in which a fixed set of rules is applied to carve away at the edges of the Possible nodes of the text

Further reduction, in which a large number of rules may be applied to further reduce the text

One reduction algorithm, text tightening, that is referred to in some of the scenarios that follow, will be defined at a later time.

Structural rules for initializing the text

Rule Ascend

Type Cell Deletion

Objects cell C (X, Y)

Condition X is not in the range [Y .. N-K+Y]

Actions Set C.State to Impossible

Rule CompleteNodes

Type Cell Deletion

Condition Nodes in range [0 .. P-1] are complete (for some P) - their augmented adjacency sets have cardinality N

Actions Set the State of all cells in row X and column X that are not the cell (X, X) to Impossible, for X in [0 .. P-1]

The application of these two rules will result in an initial text similar to the following (random graph: N = 50, K = 30, edgeProbability = 0.96; 8 complete nodes):

The blue cursor in the lower-left corner surrounds cell (0, 0).

Gray cells are Impossible. Red cells are Possible. The brighter the color of a red cell, the larger the cardinality of its local augumented adjacency set - ranging from black cells (cardinality K) to bright red cells (cardinality N).

Several scenarios and sample snapshots of the text in examples follow.

Scenario: The question is resolved after a probe following text construction - A k-clique exists.

(Random graph: N = 50, k = 30, edgeProbability = 0.96)

Processing log

Constructing the text
Probing for a k-clique (single probe, no backtracking)
    A k-clique exists:
        { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 16, 17, 19, 29, 
          30, 32, 33, 34, 35, 37, 39, 41, 43, 44, 46, 48 }
    In the original graph's labeling:
        { 0, 1, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 22, 
          24, 26, 27, 31, 34, 38, 42, 43, 44, 47, 49 }

Scenario: The question is resolved after a probe following constraint propatation - A k-clique exists.

(Random graph: N = 50, k = 30, edgeProbability = 0.96)

After initialization After constraint propagation

Processing log

Constructing the text
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Propagating constraints
    Did not determine whether a k-clique exists
Probing for a k-clique (single proble, no backtracking)
    A k-clique exists:
        { 0, 1, 2, 3, 4, 5, 6, 8, 10, 13, 15, 16, 17, 19, 21, 23, 25, 27, 
          29, 31, 33, 35, 38, 39, 40, 42, 43, 46, 47, 49 }
    In the original graph's labeling:
        { 1, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 19, 20, 22, 23, 24, 
          27, 28, 32, 35, 36, 37, 39, 40, 42, 43, 44, 46, 49 }

Scenario: The question is resolved after a probe following constraint propagation - no k-clique exists.

(Random graph: N = 50, k = 30, edgeProbability = 0.96)

After initialization After constraint propagation After text tightening

Processing log

Constructing the text
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Propagating constraints
    Did not determine whether a k-clique exists
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Tightening the text
    Cell deletion resulted in an empty column
    No k-clique exists

Scenario: The question is resolved after a probe that follows text tightening - a k-clique exists.

(Random graph: N = 50, k = 30, edgeProbability = 0.96)

After initialization After constraint propagation After text tightening

Processing log

Constructing the text
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Propagating constraints
    Did not determine whether a k-clique exists
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Tightening the text
    Did not determine whether a k-clique exists
Probing for a k-clique (single probe, no backtracking)
    A k-clique exists:
        { 0, 1, 2, 3, 4, 5, 6, 7, 9, 12, 13, 17, 19, 22, 23, 25, 26, 28, 
          29, 30, 32, 34, 35, 38, 39, 42, 43, 45, 46, 48 }
    In the original graph's labeling:
        { 0, 2, 4, 5, 6, 8, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 
          27, 30, 31, 34, 35, 39, 41, 42, 44, 45, 46, 48, 49 }

Scenario: The question remains unresolved after a probe that follows text tightening.

(Random graph: N = 50, k = 30, edgeProbability = 0.96)

After initialization After constraint propagation After text tightening

Processing log

Constructing the text
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Propagating constraints
    Did not determine whether a k-clique exists
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique
Tightening the text
    Did not determine whether a k-clique exists
Probing for a k-clique (single probe, no backtracking)
    The probe did not discover a k-clique

First in thread Previous in thread




	Home > Jabberwocky Previous Next

	Craig Holman Research Jabberwocky Quotations Contact



	Patterncraft™ and Constraint and Consequence™ are trademarks of Craig Stewart Holman Copyright © 2008 Craig Stewart Holman Copyright and Legal Notices All Rights Reserved.

Jabberwocky for May 31, 2008

What is it?

Search Approach to the k-Clique Exists problem - Introduction to the Text