-
Notifications
You must be signed in to change notification settings - Fork 0
/
ctic.tex
231 lines (205 loc) · 7.93 KB
/
ctic.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
\documentclass[utf8,notheorems]{beamer}
\usetheme[compress]{Singapore}
\usepackage[brazil]{babel}
\let\C\someundefinedcommand
\let\G\someundefinedcommand
% These two commands are defined by hyperref in file puenc.def,
% and conflict with complexity - which also defines them.
\usepackage{complexity}
\theoremstyle{definition}
\newtheorem*{definition}{Definição}
% Gambiarra para que o \Phi possua serifas horizontais,
% como o I em algumas fontes.
\DeclareSymbolFont{Gambiarrra}{U}{zeur}{m}{n}
\DeclareMathSymbol\Phi{\mathalpha}{Gambiarrra}{"08}
\begin{document}
\title{Blum Axioms and Nondeterministic Computation of Functions}
\author{Tiago Royer\inst{1} \and Jerusa Marchi\inst{1}}
\institute[UFSC]{
\inst{1}
Universidade Federal de Santa Catarina \\
Departamento de Informática e Estatística
}
\date[XXXV CTIC]{
XXXV Concurso de Trabalhos de Iniciação Científica \\
Congresso da Sociedade Brasileira de Computação --- 2016
}
\begin{frame}
\titlepage
\end{frame}
\begin{frame}
\frametitle{Máquinas de Turing e funções}
\begin{itemize}
\item Problema de decisão $\rightarrow$ Linguagem
\item Problema de busca $\rightarrow$ Função
\item Tipicamente, define-se apenas o reconhecimento de linguagens. \\
\end{itemize}
Para provar indecidibilidade/intratabilidade:
\begin{itemize}
\item Problema de busca $\rightarrow$ Problema de decisão
$\rightarrow$ Linguagem
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Cálculo não-determinístico de funções}
\begin{itemize}
\item E o cálculo de funções?
\item Definição direta para máquinas determinísticas
\item Útil, mesmo do ponto de vista teórico
\begin{itemize}
\item Usado na noção de redução
\end{itemize}
\item Mas como fazer uma máquina não-determinística \\
calcular uma função?
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Definição de Hopcroft e Ullman}
O valor da função computada por uma máquina não-determinística \\
é $x$, para uma dada entrada, se
\begin{itemize}
\item algum ramo de computação devolve $x$, e
\item nenhum ramo de computação que para devolve $x' \neq x$.
\end{itemize}
Caso contrário, deixe a função indefinida nesta entrada.
\cite[p.~313]{HopcroftUllman1979}
\end{frame}
\begin{frame}
\frametitle{Definição de Hopcroft e Ullman}
Problema: podemos computar o complemento do problema da parada.
\begin{itemize}
\item Dados uma máquina $M$ e uma entrada $w$, \\
faça dois ramos de computação:
\begin{itemize}
\item O primeiro escreve $1$ e para,
\item O segundo executa $M$ em $w$ e, se $M$ parar,
escreve $0$ e para.
\end{itemize}
\item Se $M$ não parar em $w$,
o resultado da computação é $1$;
\item Se $M$ parar em $w$,
o resultado da computação é indefinido.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Enumerações de Gödel Aceitáveis}
\begin{definition}
Seja $\mathcal P$ o conjunto das funções recursivas parciais. \\
Uma \emph{enumeração de Gödel aceitável} \\
é uma função sobrejetora \alert<2>{$\phi: \{0, 1\}^* \to \mathcal P$} que possui
\begin{itemize}
\item uma função computável $U$ tal que $U(w, x) = \phi_w(x)$ \\
(Teorema da máquina universal); e
\item uma função computável $\sigma$ tal que
$\phi_{\sigma(w, x)}(y) = \phi_w(x, y)$ \\
(Teorema $S_{mn}$).
\end{itemize}
{\cite[p.~41]{Rogers1987}}
(Notação: $\phi_w$ é a função $\phi(w)$.)
\end{definition}
\end{frame}
\begin{frame}
\frametitle{Enumerações de Gödel Aceitáveis --- Exemplos}
\begin{itemize}
\item Enumerações de máquinas de Turing
\item Qualquer linguagem de programação moderna
\item Contraexemplo: Definição de Hopcroft e Ullman
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Definição de Goldreich}
Seja $\bot$ um símbolo fora do alfabeto. \\
O valor da função computada por uma máquina não-determinística \\
é $x$, para uma dada entrada, se
\begin{itemize}
\item algum ramo de computação devolve $x$, e
\item todos os ramos param e devolvem $x$ ou $\bot$.
\end{itemize}
Caso contrário, deixe a função indefinida nesta entrada.
\cite[p.~313]{HopcroftUllman1979}
\end{frame}
\begin{frame}
\frametitle{Definição de Goldreich}
Problema: máquinas que agem de acordo com esta definição \\
podem ser facilmente invertidas;\\
portanto, se alguma máquina não-determinística resolvesse $\SAT$ \\
em tempo polinomial (de acordo com esta definição) \\
poderíamos simplesmente inverter a saída, \\
provando que $\NP = \coNP$.
\end{frame}
\begin{frame}
\frametitle{Axiomas de Blum}
\begin{definition}
Dada uma enumeração aceitável $\phi$, \\
uma \emph{medida de complexidade} é uma função parcial \\
\alert<2>{$\Phi: \{0, 1\}^* \times \{0, 1\}^* \to \mathbb N$} tal que
\begin{itemize}
\item $\Phi(w, x)$ está definido se e só se $\phi_w(x)$ o está; e \\
\item O predicado ``$\Phi(w, x) = k$'' é decidível.
\end{itemize}
\end{definition}
\cite[p.~324]{Blum1967}
(Classes de complexidade podem ser generalizadas diretamente)
\end{frame}
\begin{frame}
\frametitle{Axiomas de Blum --- Exemplos}
\begin{itemize}
\item Tempo
\item Espaço
\item Número de mudanças de estado
\item Número de vezes que uma célula da fita é alterada
\item Definição de Goldreich \\
(Problema: Classe análoga à $\NP$ não contém análogo de $\SAT$, \\
a menos que $\NP = \coNP$.)
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Definição proposta}
$\SAT$ pode ser reconhecido não-deterministicamente \\
``chutando'' uma atribuição de valores verdade. \\
Altere este algoritmo para, em vez de aceitar/rejeitar, \\
retornar $1$ e $0$, respectivamente.
\begin{itemize}
\item Fórmulas tautológicas devolverão apenas $1$
\item Fórmulas contraditórias devolverão apenas $0$
\item Fórmulas satisfazíveis, mas não tautológicas, \\
devolverão tanto $0$ quanto $1$.
\end{itemize}
A resposta certa é exatamente o máximo dentre os valores devolvidos
\end{frame}
\begin{frame}
\frametitle{Definição proposta}
\begin{definition}
Se todos os ramos de computação de $M$ em $w$ param, \\
o valor da função é o máximo dentre todos os valores devolvidos. \\
Se algum ramo não para, deixe a função de $M$ indefinida em $w$.
\end{definition}
\end{frame}
\begin{frame}
\frametitle{Definições de Krentel e Valiant}
\begin{itemize}
\item Aplicar operadores associativos à lista dos valores devolvidos
\item Classe $\OptP$, de Krentel: Máximo/Mínimo \cite{Krentel1988}
\item Classe $\#\P$, de Valiant: Cardinalidade \cite{Valiant1979}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Considerações finais}
\begin{itemize}
\item Algumas definições de cálculo não-determinístico de funções
que não são ``razoáveis'' ou ``eficientes''
\item É possível formalizar a exigência de ``razoabilidade''
e ``eficiência''
\item É possível definir como uma máquina não-determinística
pode calcular uma função, satisfazendo estas exigências.
\end{itemize}
\end{frame}
\begin{frame}[allowframebreaks]
\frametitle{Bibliografia}
\bibliographystyle{plain}
\bibliography{bib/bibliography}
\end{frame}
\begin{frame}
\titlepage
\end{frame}
\end{document}