2005 Tech Reports
AUTHOR: Bruce Litow
TITLE:
NP
union co-NP has Polynomial Circuit Size
ABSTRACT:
We show that NP union co-NP, the first level of the polynomial
time hierarchy, has polynomial circuit size.
AUTHOR: Bruce Litow
TITLE:
Rational
Weight Finite Automaton Bounded-Length Behavior Equality
ABSTRACT:
It has been shown that deciding whether the length n bounded
behaviors of two arbitrary rational weight finite automata are unequal
is in random nO(1) time.
Here we refine that result and show that on an algebraic number
conjecture it is in fact in nO(1) time.
This result can be applied to show that deciding whether two unambiguous
context-free grammars generate the same set of length n words is
also in nO(1) time on the conjecture.
AUTHORS: Bruce Litow and David Laing
TITLE:
A
Census Algorithm for Chinese Remainder Pseudorank with Experimental
Results
ABSTRACT:
This paper describes a polynomial time census algorithm for chinese
remainder pseudorank.
That is, we can rapidly estimate the density of integers with either
good or bad pseudorank.
The pseudorank of an integer is an important approximation technique
that makes possible efficient parallel computation of the standard order
relation on integers in chinese remainder (also known as multiresidue)
representation.
In this paper we also describe an implementation of the algorithm in C
and report on its performance, and on the census information for chinese
remainder representation systems up to 989-bit integers.
© James Cook University, Australia
School of Information Technology Home Page