Pseudo-polynomial time
id:
pseudo-polynomial-time-286-8471884
title:
Pseudo-polynomial time
text:
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input—but not necessarily in the length of the input, which is the case for polynomial time algorithms. In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP-complete problem with known pseudo
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Pseudo-polynomial_time
date created:
date modified:
2023-12-04T07:57:22Z
main entity:
{"identifier":"Q155291","url":"https://www.wikidata.org/entity/Q155291"}
image:
fields total:
13
integrity:
13