ECCC-Report TR17-072https://eccc.weizmann.ac.il/report/2017/072Comments and Revisions published for TR17-072en-usSun, 20 Aug 2017 17:29:32 +0300
Revision 1
| Better Complexity Bounds for Cost Register Machines |
Eric Allender,
Pierre McKenzie,
Andreas Krebs
https://eccc.weizmann.ac.il/report/2017/072#revision1Cost 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.Sun, 20 Aug 2017 17:29:32 +0300https://eccc.weizmann.ac.il/report/2017/072#revision1
Paper TR17-072
| Better Complexity Bounds for Cost Register Machines |
Eric Allender,
Pierre McKenzie,
Andreas Krebs
https://eccc.weizmann.ac.il/report/2017/072Cost 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.Tue, 25 Apr 2017 17:07:16 +0300https://eccc.weizmann.ac.il/report/2017/072