---------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------
Título: Probabilistic Entailment and Probabilistic Satisfiability: a Report of Work in Progress
Palestrante: Marcelo Finger
Data: 03/09/2009, 14h00
Local: Sala 243A, IME-USP
Resumo:
--------------
We report on recent developments (still work in progress) on the notions of probabilistic entailment and its application to the search of new solutions to the problem of probabilistic satisfiability (PSAT), which is studied in a setting with no independence pressuposition.
PSAT is an NP-problem which, however, tends to have solutions that are much harder than usual NP-complete problems, such as SAT. In the light of recent developments of very efficient SAT solvers, we aim to find polynomial time reductions of PSAT into SAT, which must exists. Usual algorithms found in the literature are based on modification of linear programming, as the problem is originally described as an exponentially large linear program.
This investigation explores the notion of __probabilistic entailment__, and focuses on the interface between logic, probability and linear algebra. One of the central results that unites all these is, in fact, based on combinatorics. This is still work in progress, and we hope to present the current line of research, some interesting results and discuss what is still missing.
Todos são benvindos
--
Marcelo Finger http://www.ime.usp.br/~mfinger
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------
Título: Probabilistic Entailment and Probabilistic Satisfiability: a Report of Work in Progress
Palestrante: Marcelo Finger
Data: 03/09/2009, 14h00
Local: Sala 243A, IME-USP
Resumo:
--------------
We report on recent developments (still work in progress) on the notions of probabilistic entailment and its application to the search of new solutions to the problem of probabilistic satisfiability (PSAT), which is studied in a setting with no independence pressuposition.
PSAT is an NP-problem which, however, tends to have solutions that are much harder than usual NP-complete problems, such as SAT. In the light of recent developments of very efficient SAT solvers, we aim to find polynomial time reductions of PSAT into SAT, which must exists. Usual algorithms found in the literature are based on modification of linear programming, as the problem is originally described as an exponentially large linear program.
This investigation explores the notion of __probabilistic entailment__, and focuses on the interface between logic, probability and linear algebra. One of the central results that unites all these is, in fact, based on combinatorics. This is still work in progress, and we hope to present the current line of research, some interesting results and discuss what is still missing.
Todos são benvindos
--
Marcelo Finger http://www.ime.usp.br/~mfinger
Nenhum comentário:
Postar um comentário