Low (complexity)
id:
low-complexity-289-17127460
title:
Low (complexity)
text:
In computational complexity theory, a language B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems i
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Low_(complexity)
date created:
date modified:
2023-02-21T16:59:20Z
main entity:
{"identifier":"Q6692803","url":"https://www.wikidata.org/entity/Q6692803"}
image:
fields total:
13
integrity:
13