Cryptography Reference
In-Depth Information
Exercise 8.2.
We represent triplets of integers
(
a
,
b
,
c
)
by bitstrings
(
a
0
,
b
0
,
c
0
,
a
1
,
b
1
,
c
1
,...,
a
n
,
b
n
,
c
n
)
such that
n
a
i
2
i
a
=
i
=
0
n
b
i
2
i
b
=
i
=
0
n
c
i
2
i
c
=
i
=
0
Prove that the language of all
(
a
,
b
,
c
)
triplets such that c
=
a
+
b is regular.
Exercise 8.3.
We represent pairs of integers
(
a
,
b
)
by bitstrings
(
a
0
,
b
0
,
a
1
,
b
1
,...,
a
n
,
b
n
)
such that
n
a
i
2
i
a
=
i
=
0
n
b
i
2
i
b
=
i
=
0
Derive a Turing machine which takes a pair of integers
(
a
,
b
)
as an input and outputs
+
a bitstring which represents a
b.
Do the same with the multiplication a
×
b.
Exercise 8.4.
We represent a graph G whose vertices set is
{
1
,
2
,...,
n
}
by its adja-
cency matrix M. Here M is of size n
n where M
i
,
j
is a bit set to one if and only if
the i -th vertex and the j -th vertex are connected by an edge in G. The matrix M is
itself represented by a bitstring of length n
2
which is obtained by reading the matrix
row by row, column by column. We say that a graph G is c-colorable if there exists a
mapping C from
×
{
1
,
2
,...,
n
}
to
{
1
,
2
,...,
c
}
such that there exists no edge
(
i
,
j
)
such
that C
(
i
)
=
C
(
j
)
: two connected vertices always have different colors.
We let L be the language of all 2-colorable graphs. Prove that L is in P by deriving
an algorithm which yields whether a given graph is 2-colorable or not.
We let L be the language of all 3-colorable graphs. Prove that L is NP-complete.
Search WWH ::
Custom Search