Log-space reduction
id:
log-space-reduction-243-18062989
title:
Log-space reduction
text:
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers. It is possible that such a machine may not have space to write down its own output, so the only requirement is that any given bit of the output be computable in log-space. Formally, this reduction is executed via a log
brand slug:
wiki
category slug:
encyclopedia
description:
Type of computational algorithm
original url:
https://en.wikipedia.org/wiki/Log-space_reduction
date created:
date modified:
2022-12-18T14:57:46Z
main entity:
{"identifier":"Q448582","url":"https://www.wikidata.org/entity/Q448582"}
image:
fields total:
13
integrity:
14