Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-072 | 20th August 2017 17:29

Better Complexity Bounds for Cost Register Machines

RSS-Feed




Revision #1
Authors: Eric Allender, Andreas Krebs, Pierre McKenzie
Accepted on: 20th August 2017 17:29
Downloads: 27
Keywords: 


Abstract:

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC1 when the semiring is (Z,+,×) or (?*,max,?). This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC1 versus GapNC1.



Changes to previous version:

Technical typos and one serious error corrected.


Paper:

TR17-072 | 25th April 2017 17:06

Better Complexity Bounds for Cost Register Machines





TR17-072
Authors: Eric Allender, Andreas Krebs, Pierre McKenzie
Publication: 25th April 2017 17:07
Downloads: 166
Keywords: 


Abstract:

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC1 when the semiring is (Z,+,×) or (?*,max,?). This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC1 versus GapNC1.



ISSN 1433-8092 | Imprint