Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

suey

M.Sc.

  • "suey" is female
  • "suey" started this thread

Posts: 485

Date of registration: Sep 29th 2009

1

Wednesday, June 8th 2011, 5:24pm

KvA-Testat

Hallo, der epix und ich sitzen gerade am KvA-Testat Nummer 1.
Wie ist das eigentlich gemeint bei Aufgabe 1c):

Hinweis zum Härte-Beweis: Gehen Sie hierbei zunächst von einer erfüllbaren Klausel
aus und konstruieren Sie anschließend eine Formel , die
genau dann eine exakt erfüllende Belegung besitzt, wenn c erfüllbar ist. Betrachten Sie
hierbei zum einen alle möglichen erfüllenden Belegungen und zeigen Sie jeweils, dass
immer eine exakt erfüllende Belegung hat. Zum anderen zeigen Sie, dass
keine exakt erfüllende Belegung hat, wenn c unerfüllbar ist. f wird hierbei
mehr Variablen als nur die aus c beinhalten.

Was uns momentan schleierhaft ist:
Wenn c unerfüllbar ist und f keine exakt erfüllende Belegung haben soll, kann f dann trotzdem erfüllbar sein durch nicht-exakt erfüllbare Belegungen?
Und wozu sollen diese "mehr Variablen als nur die aus c" dienen? Verändern tun sie die Erfüllbarkeit von f doch eigentlich nicht, da diese nur von den anderen Variaben abhängt, oder?

Edit: schöner getext ;)

This post has been edited 2 times, last edit by "suey" (Jun 8th 2011, 5:28pm)

  • Send private message

hamena314

Zerschmetterling

  • "hamena314" is male

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

2

Wednesday, June 8th 2011, 6:00pm

Ich hab's mir noch nicht angeschaut, aber sind damit vielleicht diese "durchgeschleiften" Variablen gemeint, die wir z.b. bei NAE-3SAT verwendet haben?
Also sowas wie (l1, l2, z1) ^ (~z1, l3, z4) ^...

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

3

Wednesday, June 8th 2011, 7:17pm

Quoted from "suey"

Und wozu sollen diese "mehr Variablen als nur die aus c" dienen? Verändern tun sie die Erfüllbarkeit von f doch eigentlich nicht, da diese nur von den anderen Variaben abhängt, oder?

Genau, die Erfüllbarkeit wird nicht verändert. Die dienen lediglich dazu, dass wenn es eine erfüllende Belegung für c gibt, auch eine exakt erfüllende für f(l1,l2,l3). Den es gibt ja offensichtlich viele erfüllende Belegungen für c, die nicht exakt erfüllend sind. Im Prinzip ist die Idee so ähnlich wie hamena geschrieben hat, nur ein wenig komplizierter. Aber nichts, dass man durch etwas tüfteln nicht rauskriegen kann.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message