P3 - SoSe 18 PDF

Preview

Summary

SoSe 18...

Description

at Bochum Ruhr-Universit¨ ur Kryptologie und IT-Sicherheit Lehrstuhl f¨ Prof. Dr. Alexander May Dr. Felix Heuer Alexander Helm Imane Ehsanifatmesari

Pr¨ asenz¨ ubungen zur Vorlesung

Diskrete Mathematik II SS 2018

Blatt 3 / 28./29. Mai 2018 AUFGABE 1: Wir definieren die Sprache ( Teilung :=

(m1 , . . . , mn ) ∈ Nn : ∃s1 , . . . , sn ∈ {0, 1} mit

n X i=1

n X si mi = (1 − si ) · mi i=1

)

.

Zeigen Sie: Teilung ≤p SubsetSum. AUFGABE 2: Sei Σ ein Alphabet und A, B ⊆ Σ∗ Sprachen mit A ≤p B. Zeigen Sie: B ∈ NP ⇒ A ∈ NP .

AUFGABE 3: Betrachten Sie die Sprache Half-Clique := {G | G = (V, E), |V | ist gerade und G besitzt eine

|V | -Clique.} 2

(a) Zeigen Sie Clique ≤p Half-Clique. andigkeit von Half-Clique gezeigt (b) Was ist noch zu zeigen, damit Sie die N P-vollst¨ haben?...