Transformacja pseudowielomianowa – pojęcie wykorzystywane w teorii złożoności obliczeniowej do dowodzenia silnej NP-zupełności problemów decyzyjnych podobnie do zastosowania transformacji wielomianowej przy dowodzeniu NP-zupełności.
Definicja formalna Niech i będą problemami decyzyjnymi, i oznaczają ich odpowiednie dziedziny, a i podzbiory odpowiednich dziedzin składające się z tych instancji, dla których odpowiedzią jest „TAK”. Niech ponadto oznacza największą liczbę w opisie instancji a rozmiar instancji
Transformacją pseudowielomianową problemu do problemu nazywa się funkcję
spełniającą następujące warunki: Funkcja przekształca poprawne instancje na poprawne instancje tzn.
Funkcja daje się obliczyć w czasie ograniczonym przez wielomian od i Istnieje taki wielomian że
Istnieje taki wielomian dwóch zmiennych że
Intuicja Intuicyjna interpretacja warunków wymienionych w definicji powyżej jest następująca.
Warunek pierwszy to wymaganie, by rozwiązanie, rozumiane tu jako odpowiedź „TAK” lub „NIE”, problemu powstałego po transformacji było takie samo jak rozwiązanie problemu transformowanego. Pozwala to na wyciągnięcie wniosków o rozwiązaniu problemu transformowanego na podstawie rozwiązania problemu powstałego po transformacji.