Question Answering by Humans and Machines: A Complexity-theoretic View

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F19%3A00505732" target="_blank" >RIV/67985807:_____/19:00505732 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.tcs.2018.08.012" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2018.08.012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2018.08.012" target="_blank" >10.1016/j.tcs.2018.08.012</a>

Result language

angličtina

Original language name

Question Answering by Humans and Machines: A Complexity-theoretic View

Original language description

Question-answering systems like Watson beat humans when it comes to processing speed and memory. But what happens if we compensate for this? What are the fundamental differences in power between human and artificial agents in question answering? We explore this issue by defining new computational models for both agents and comparing their computational efficiency in interactive sessions. Concretely, human agents are modeled by means of cognitive automata, augmented with a form of background intelligence which gives the automata the possibility to query a given Turing machine and use the answers from one interaction to the next. On the other hand, artificial question-answering agents are modeled by QA-machines, which are Turing machines that can access a predefined, potentially infinite knowledge base (‘advice’) and have a bounded amount of learning space at their disposal. We show that cognitive automata and QA-machines have exactly the same potential in realizing question-answering sessions, provided the resource bounds in one model are sufficient to match the abilities of the other. In particular, polynomially bounded cognitive automata with background intelligence (i.e. human agents) prove to be equivalent to polynomially bounded QA-machines with logarithmic learning space. It generalizes Pippenger's theorem on the computational power of switching circuits (without background intelligence) to a foundational result for question answering in cognitive science. The framework reveals why QA-machines have a fundamental advantage.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Volume of the periodical

777

Issue of the periodical within the volume

19 July

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

10

Pages from-to

464-473

UT code for WoS article

000473372800030

EID of the result in the Scopus database

2-s2.0-85054352634