Information Technology Reference
In-Depth Information
log
p
b
(
)
−
+
(
{
=
}
)
G
F
log
L
F
x
b
log
L
(
F
ˇ
{
x
=
0
}
)
+
L
(
F
ˇ
{
x
=
1
}
)
=
+
log
L
(
F
{
x
=
b
}
)
L
(
F
ˇ
{
x
=
b
}
)
=
log
(
L
(
F
ˇ
{
x
=
0
}
)
+
L
(
F
ˇ
{
x
=
1
}
))
log
L
(
F
).
We can see that the asymmetric game can improve the size lower bounds for
tree-like resolution for the pigeon hole principle achieved by using the original game
[
BGL10
]. For this we analyze the asymmetric game on PHP formulas and then use
Theorem 3.2.
PHP
n
,
Theorem 3.4
Fo r m
>
n
,
G
(
¬
c
0
,
c
1
)
=
(
n
log
n
)
Proof
We give a simplified proof from [
Bey11
] describing a strategy for Delayer for
which the number of scored points is
(
)
n
log
n
.
ↆ[
]
ˇ
For
i
m
we define the function
h
i
that for a partial assignment
h
i
(ˇ)
=|{
k
ↆ[
n
]|
ˇ(
x
i
,
k
)
=
0 and
ˇ(
x
j
,
k
)
∩=
1 for all
j
ↆ[
m
]}|
.
h
i
(ˇ)
indicates the number of holes that are still free but are excluded for pigeon
i
under
.
The strategy of Delayer for the variable
x
i
,
j
when the partial assignment con-
structed so far is
ˇ
, is the following:
If there is some other variable
x
i
∧
,
j
assigned to 1 (hole
j
is already used) or there
is some
x
i
,
j
∧
assigned to 1 (pigeon
i
already has a hole) then set
x
i
,
j
to 0 (by setting
the weights to
ˇ
n
2
(
1
,
0
)
). Otherwise if
h
i
(ˇ)
then set
x
i
,
j
to 1. Otherwise set the
. The values of
p
0
and
p
1
are the same for all the variables
satisfying this property and will be specified later.
Intuitively, when the number of free holes excluded for pigeon
i
are at least
2
then Delayer tries to put
i
in a free hole. As in Lemma 2.2 with this strategy only
p
0
p
1
weights of
x
i
,
j
to
(
,
)
a clause of type 1
j
=
1
x
i
,
j
can be falsified. We show that when this happens at
the end of the game, at least
n
2
variables have been assigned to 1. Consider the last
round
r
after which
h
i
(ˇ
r
)<
n
n
2
, then there are
less than
2
holes that are free for pigeon
i
and therefore more than
2
are occupied.
The corresponding variables are set to 1. Otherwise let
z
be the number of variables
2
.
If at the end of the game
h
i
(ˇ
r
)<
in
j
=
1
x
i
,
j
set to 0 after round
r
. There are exactly
2
of them that correspond to
free holes excluded for pigeon
i
. For the other
z
n
2
variables the corresponding hole
is already occupied, that is, there is a variable for each of these holes set to 1. After
round
r
every time one of the
n
−
z
remaining variables
x
i
,
j
issetto0in
j
=
1
x
i
,
j
this is done by Delayer and because there is some other variable
x
i
∧
,
j
already set to
1. The number of 1's at the end of the game is then at least
z
−
n
2
n
−
+
n
−
z
=
2
.
n
W.l.o.g. let us call the first
2
variables that are set to 1 at the end of the game by
n
x
i
,
j
i
,
ↆ
...
2
.
We analyze now howmany points Delayer scores for each of them.
If variable
x
i
,
j
i
has been assigned by Prover, then Delayer scores
i
1
p
1
points.
If it is Delayer the one who gave the variable value 1, then at that point there were at
least
−
log
(
)
n
2
free holes that were excluded for pigeon
i
. All the 0's indicating the exclusion,
