Category Archives: research

image-heidelberg

The complexity of complexity

The paper “On the complexity of automatic complexity” is to appear in Theory of Computing Systems, in a post-conference journal issue for Computability, Complexity and Randomness 2015 held in Heidelberg, Germany.

While it is not known whether the set of strings of maximal nondeterministic automatic complexity is NP-complete (hence the paper is called “On the complexity…” rather than just “The complexity…”), the paper shows that the more general problem for automatic complexity of equivalence relations is NP-complete. It is also shown that the set of highly complex strings is not context-free.

london1

Shift registers fool finite automata @ WoLLIC 2017

LFSRs (linear feedback shift registers) are popular pseudorandomness generators.
In a new project we show that they generate output (often called $m$-sequences) of maximal (nondeterministic path-based) automatic complexity. At this point we have an experimental result, one which would have probability $2^{-93}$ to occur “by chance”, as well as a theoretical but sub-optimal result.

Moreover, an $m$-sequence of length 31 provides an example of a word $x$ such that
$$
A^-(x)=A_N(x)+2
$$
where $A_N$ is nondeterministic path-based automatic complexity, and $A^-$ is non-total deterministic automatic complexity.
Such an example (where $A^-(x)-A_N(x)>1$) was not known before the consideration of LFSRs in this area. That consideration was an idea of Jason Castiglione.

The paper has been accepted at WoLLIC 2017.

This project was presented at the poster session of the SIAM Conference on Discrete Mathematics 2016 in Atlanta, Georgia. The session was otherwise dominated by interesting work on RNA pseudoknots and chord diagrams (3 out of 6 posters) which in the case of the work of the Biocomplexity Institute researchers Ricky Chen and Thomas Li involves modeling with multiply context-free grammars.

2326007202794064150-account_id=1

Superposition as memory @ UCNC17

Imagine a lock with two states, locked and unlocked, which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states locked and unlocked, where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan–Schur lemma that a similar lock is not possible for $n=60$.

Details in the paper: Superposition as memory: unlocking quantum automatic complexity which appeared in the Lecture Notes in Computer Science volume of the conference Unconventional Computation and Natural Computation (UCNC) 2017.

Slides

group

Computability Theory List Server

As of June 15, 2006, we are not posting emails for ANY third party. To post one must be a subscriber to the list. If you are having problems first confirm yourself as subscriber (directions are below) and if that does not work please remove yourself from the list and resubscribe. Directions on how to do this can be found by following the links below.

To use the list just send email to comp-thy@lists.hawaii.edu, the list server will take care of the rest. You must be a member of the list to send mail to the list. Anyone is free to join the list. Use the list just as you would a normal email address expect for the fact that everyone subscribed to the list will receive a copy of your email. It may take some time before your message reaches everyone on the list. You may use the list as you see fit.

Although it would be best if it were used for short announcements of interest to all computability theorists.

A WORD OF CAUTION: Large files cause problems for many mailers.

Using the list server

The list server at University of Hawaii maintains the mailing list. It can do many things. For example, it can be used to subscribe, unsubscribe, or look at the archive for the list. These and others tasks are completed by issuing commands to the list server. The easiest way to do this is do use the WWW interface at listserv.hawaii.edu.

Note only COMP-THY subscribers may access the list archives. When you attempt to access the archives, you will be asked for your email address and a password. If you already have a password for listserv.hawaii.edu, use that password to access the COMP-THY list. If you do not have a password for listserv.hawaii.edu, go to listserv.hawaii.edu to sign up.

Maui-Hawaii

Few paths, fewer words: model selection with automatic structure functions

The paper “Kolmogorov structure functions for automatic complexity in computational statistics” appeared in the Lecture Notes in Computer Science proceedings of the conference COCOA 2014, Maui, Hawaii.
The paper then appeared in the journal Theoretical Computer Science 2015.

The ideas are implemented in the Structure function calculator.

A new paper Few paths, fewer words: model selection with automatic structure functions has been conditionally accepted for publication in Experimental Mathematics.

Some slides

group

Covering the computable sets

I participated in the workshop on Algorithmic Randomness in Singapore and the conference on Computability, Complexity and Randomness.

With host Frank Stephan and fellow participant Sebastiaan Terwijn we wrote a paper entitled Covering the recursive sets which appeared in Lecture Notes in Computer Science, Conference on Computability in Europe, 2015, and has now been published in Annals of Pure and Applied Logic.

20160929_115658

ビヨーン教授の最新研究の概要

この記事は、ハワイ大学のビヨーン・ヒュース-ハンセン教授(Prof. Bjørn Kjos-Hanssen)のオートマトン複雑性に関する最新の研究について、日本の読者向けに概要をまとめたものである。

1. 目的
オートマトン複雑性に関する研究の目的は、特定の文字列を受領するオートマトンで、できるだけ状態数が少なく、その文字列と同じ長さの他の文字列をできるだけ受領しないオートマトンの効率のよい検索方法を見つけることである。言い換えれば、コルモゴロフ構造関数の考え方によるモデル選択をオートマトン上でより効率よく行うことである。
コルモゴロフ構造関数については歴史の項目で後述する。
モデル選択とは、自然界にある文字列でモデル化できるものが発見されたときに、背景となっているその文字列を生成する仕組みをオートマトンでモデル化することを指す。その文字列を受理し、他の文字列をできるだけ受理しないオートマトンを考えることができれば、そのオートマトンがモデルとして適切だと推測することができる。

2. オートマトン複雑性分野の歴史
オートマトン複雑性分野は近年研究の始まった分野であり、新規性が期待される。
当分野の主な歴史は、以下の通りである。

1960年代末 コルモゴロフ複雑性(Kolmogorov Complexity)
チューリングマシンにおける文字列の複雑性をそれに最適なプログラムの長さで定義
1973年 コルモゴロフ構造関数(Kolmogorov Structure Function)
文字列に対してプログラムとそのプログラムが受領する文字列の数を対応付ける関数で、文字列のモデリングの適切さを測る
2001年 ShallitとWangによるオートマトン複雑性(Automatic Complexity by Shallit and Wang)
コルモゴロフ複雑性を、オートマトンに拡張。オートマトンでの複雑性をその文字列を受領し、他の同じ長さの文字列を受領しないオートマトンの最小の状態数で定義
2014年 Vereshchagin のオートマトン複雑性上での構造関数(Vereshchagin structure function for Automatic complexity)
オートマトン上での構造関数を、オートマトンの状態数と特定の文字列を受領するその状態数のオートマトンが受領する最小の文字列数の対応として定義

3. 当研究に期待される成果
現在、文字列に対する最適なモデルの推測の効率のよいアルゴリズムは発見されていないが、この研究によって、より正確に効率よく推測できるようになる。

4. 当分野において期待されるインパクト
オートマトン複雑性上での構造関数の計算速度の向上が期待されている。

5. 諸科学において期待されるインパクト
構造関数はco-NP問題であるため、未解決問題であるP=NP、co-NP=NPなどの問題についての理解を深めることができる。

当研究は現在進行中で、公開時期は未定である。
引き続きビヨーン教授の最新の情報に注目していただきたい。

 

小林 佐保,千葉大学 理学部 数学・情報数理学科
Saho Kobayashi, Undergraduate, Department of Mathematics and Informatics, Faculty of Science, Chiba University