Datei:NP-hardness of pattern language membership.pdf
Größe der JPG-Vorschau dieser PDF-Datei: 799 × 182 Pixel. Weitere Auflösungen: 320 × 73 Pixel | 1.285 × 293 Pixel
Originaldatei (1.285 × 293 Pixel, Dateigröße: 17 KB, MIME-Typ: application/pdf)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
| Beschreibung |
English: Shows a reduction of the 1-in-3-SAT problem to the problem of deciding whether a given string is a member of a given pattern language. The construction is inspired by Dana Angluin's original proof (Thm.3.6 in "Finding Patterns Common to a Set of Strings", JCSS 21/1980), but simplified by using 1-in-3- rather than plain 3-SAT. |
| Datum | |
| Quelle | Eigenes Werk |
| Urheber | Jochen Burghardt |
| Andere Versionen |
|
| PDF‑Erstellung |
LaTeX source code
|
|---|
\documentclass[12pt]{article}
\usepackage[pdftex]{color}
\usepackage[paperwidth=218mm,paperheight=50mm]{geometry}
\setlength{\topmargin}{-45mm}
\setlength{\textwidth}{216mm}
\setlength{\textheight}{51mm}
\setlength{\oddsidemargin}{-25mm}
\pagestyle{empty}
\begin{document}
\definecolor{fSep} {rgb}{0.00,0.00,0.50} % separating 0
\definecolor{fPos} {rgb}{0.00,0.50,0.00} % true
\definecolor{fNeg} {rgb}{0.50,0.00,0.00} % false
\newcommand{\0}{\textcolor{fSep}{\bf 0}} % separating 0
\newcommand{\1}[1]{\overline{#1}} % negation
\newcommand{\2}[1]{\textcolor{fNeg}{#1}} % false
\newcommand{\3}[1]{\textcolor{fPos}{#1}} % true
$$\begin{array}{l*{32}{c}}
\bf CNF:
&&&&&&&&&&&&&&&&
& & \multicolumn{4}{c}{(\1w \!\lor\! x \!\lor\! \1y)}
& \land & \multicolumn{4}{c}{( w \!\lor\! y \!\lor\! z)}
& \land & \multicolumn{4}{c}{( x \!\lor\! \1y \!\lor\! \1z)}
\\
\\
\bf Pattern:
& \0 & \multicolumn{3}{c}{wW}
& \0 & \multicolumn{3}{c}{xX}
& \0 & \multicolumn{3}{c}{yY}
& \0 & \multicolumn{3}{c}{zZ}
& \0 & \multicolumn{4}{c}{W x Y}
& \0 & \multicolumn{4}{c}{w y z}
& \0 & \multicolumn{4}{c}{x Y Z}
& \0
\\
\bf String:
& \0 & 1 & 1 & 1
& \0 & 1 & 1 & 1
& \0 & 1 & 1 & 1
& \0 & 1 & 1 & 1
& \0 & 1 & 1 & 1 & 1
& \0 & 1 & 1 & 1 & 1
& \0 & 1 & 1 & 1 & 1
& \0
\\
\\
\bf Solution:
&& \multicolumn{3}{c}{\1w=1}
&& \multicolumn{3}{c}{\1x=1}
&& \multicolumn{3}{c}{ y=1}
&& \multicolumn{3}{c}{\1z=1}
& & \multicolumn{4}{c}{(1 \!\lor\! 0 \!\lor\! 0)}
& \land & \multicolumn{4}{c}{(0 \!\lor\! 1 \!\lor\! 0)}
& \land & \multicolumn{4}{c}{(0 \!\lor\! 0 \!\lor\! 1)}
\\
\\
\cline{3-5}
\cline{7-9}
\cline{11-13}
\cline{15-17}
\cline{19-22}
\cline{24-27}
\cline{29-32}
& \0 & \multicolumn{1}{|c|}{\2w} & \multicolumn{2}{|c|}{\3W}
& \0 & \multicolumn{1}{|c|}{\2x} & \multicolumn{2}{|c|}{\3X}
& \0 & \multicolumn{2}{|c|}{\3y} & \multicolumn{1}{|c|}{\2Y}
& \0 & \multicolumn{1}{|c|}{\2z} & \multicolumn{2}{|c|}{\3Z}
& \0 & \multicolumn{2}{|c|}{\3W} & \multicolumn{1}{|c|}{\2x} & \multicolumn{1}{|c|}{\2Y}
& \0 & \multicolumn{1}{|c|}{\2w} & \multicolumn{2}{|c|}{\3y} & \multicolumn{1}{|c|}{\2z}
& \0 & \multicolumn{1}{|c|}{\2x} & \multicolumn{1}{|c|}{\2Y} & \multicolumn{2}{|c|}{\3Z}
& \0
\\
& \0 & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31}
& \0 & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31}
& \0 & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31} & \multicolumn{1}{|c|}{\21}
& \0 & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31}
& \0 & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31} & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c|}{\21}
& \0 & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31} & \multicolumn{1}{|c|}{\21}
& \0 & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c|}{\21} & \multicolumn{1}{|c }{\31} & \multicolumn{1}{ c|}{\31}
& \0
\\
\cline{3-5}
\cline{7-9}
\cline{11-13}
\cline{15-17}
\cline{19-22}
\cline{24-27}
\cline{29-32}
\end{array}$$
\end{document}
% finding a 1-in-3-satisfiable CNF:
w x y z W X Y Z WxY wyz xYZ
--------------------------------------------------
%0 0 0 0 1 1 1 1 101 000 011
%0 0 0 1 1 1 1 0 101 001 010
0 0 1 0 1 1 0 1 100 010 001
%0 0 1 1 1 1 0 0 100 011 000
%0 1 0 0 1 0 1 1 111 000 111
%0 1 0 1 1 0 1 0 111 001 110
%0 1 1 0 1 0 0 1 110 010 101
%0 1 1 1 1 0 0 0 110 011 100
%1 0 0 0 0 1 1 1 001 100 011
%1 0 0 1 0 1 1 0 001 101 010
%1 0 1 0 0 1 0 1 000 110 001
%1 0 1 1 0 1 0 0 000 111 000
%1 1 0 0 0 0 1 1 011 100 111
%1 1 0 1 0 0 1 0 011 101 110
%1 1 1 0 0 0 0 1 010 110 101
%1 1 1 1 0 0 0 0 010 111 100
|
Lizenz
Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:
Diese Datei ist unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert“ lizenziert.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
| Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
|---|---|---|---|---|---|
| aktuell | 22:24, 5. Nov. 2013 |  | 1.285 × 293 (17 KB) | Jochen Burghardt | added rightmost 0es |
| 21:39, 5. Nov. 2013 |  | 1.227 × 293 (17 KB) | Jochen Burghardt | User created page with UploadWizard |
Dateiverwendung
Keine Seiten verwenden diese Datei.