Tilbake til søkeresultatene

FRINATEK-Fri prosj.st. mat.,naturv.,tek

Symbolic Algorithms: A Parameterized Approach

Alternativ tittel: Symboliske algoritmer: En parameterisert tilnærming

Tildelt: kr 12,0 mill.

De aller fleste forskningen innen algoritmer er viet til utvikling av algoritmer for beregningsproblemer hvis forekomster er representert eksplisitt. Tenk for eksempel på problemet med å summere to vektorer x og y. Den mest naturlige og eksplisitte måten å representere slike inngangsvektorer på er å spesifisere hver koordinat for hver vektor individuelt. Resultatet av summeringen er deretter vektoren x+y oppnådd ved å summere hver oppføring av x med den tilhørende oppføringen av y. Symboliske algoritmer, derimot, arbeider med beregningsproblemer hvis forekomster er representert implisitt. Intuitivt er en implisitt representasjon av en inngang en komprimert versjon av inngangen. I eksemplet ovenfor vil målet være å utvikle en algoritme som tar komprimerte representasjoner C (x) og C (y) av vektorene x og y og beregner en representasjon C (x+y) av resultatet x+y. Ideelt sett vil en slik symbolsk algoritme beregne C (x+y) uten å måtte dekomprimere C (x) og C (y). Dette kan føre til en betydelig økonomi av beregningsressurser. Målet med dette prosjektet er å starte en systematisk studie av symbolske algoritmer ved hjelp av verktøy fra feltet parameterisert kompleksitetsteori. Vi ser for oss at resultatene våre vil kaste nytt lys over viktige utfordringer innen kunstig intelligens.

The goal of this project is to initiate a systematic study of the field of symbolic algorithms using tools from parameterized complexity theory. By symbolic algorithms, we mean algorithms that are used to decide properties about objects that are implicitly represented using data structures such as automata, decision diagrams, circuits, linear programs, etc. The main distinction between such algorithms and algorithms that operate on explicitly given data structures is the fact that symbolic data structures may be used to represent combinatorial objects that can be much larger than the size of the input. For instance, certain graphs with 2^O(n) vertices can be represented by decision diagrams with O(n)-bits. In this project, we will develop a new set of tools for the symbolic representation of classes of combinatorial objects and for the development of algorithms deciding combinatorial properties about these classes. We envision applications to the fields of automated deduction, automated theorem proving, knowledge representation, and related subfields of artificial intelligence.

Budsjettformål:

FRINATEK-Fri prosj.st. mat.,naturv.,tek