Skip to main content
Computer Science

Return to Answer

fixed dead link with (permanent) DOI link
Source Link
edit approved Apr 12, 2016 at 0:56
argentpepper
edit approved Apr 12, 2016 at 0:56
argentpepper
  • 255
  • 2
  • 8

Buss In his 1987 paper "The Boolean formula value problem is in ALOGTIME", Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.

Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.

In his 1987 paper "The Boolean formula value problem is in ALOGTIME", Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.

Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.