Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Factoring and testing primes in small space

Viliam Geffert;  Dana Pardubská — 2013

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We discuss how much space is sufficient to decide whether a unary given number is a prime. We show that (log log ) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log ) and also in accept–ASPACE(log log ). Moreover, if the given is composite,...

Measuring the problem-relevant information in input

Stefan Dobrev;  Rastislav Královič;  Dana Pardubská — 2009

RAIRO - Theoretical Informatics and Applications

We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and...

Page 1

Download Results (CSV)