Аббревиатура на все случаи жизни

В одной из последних лекций на образовательном ресурсе Coursera проф. Тим Рафгарден поведал о любопытном факте. Когда математики и программисты второй половины XX века думали о том, как назвать те задачи, которые мы привыкли именовать NP-полными, среди прочих был предложен следующий вариант - английская аббревиатура PET. Вариант, как видим, не прижился, однако достоин упоминания вследствие лингвистической находчивости авторов.

В чем же эта находчивость проявляется?
Как известно, доказательство неравенства классов P и NP еще не получено, и поэтому нельзя аргументированно заявлять о том, что эти задачи можно решить только экспоненциально. Поэтому PET можно расшифровать как "probably exponential time".

Но прогресс не стоит на месте и когда-нибудь это доказательство может быть получено. Тогда аббревиатура останется прежней, поменяется лишь расшифровка - "provably exponential time". Теперь давайте представим что дед мороз существует и P = NP. И даже в этом случае аббревиатуру не пришлось бы менять - задачи стали бы называть "previously exponential time".

Привычный  нам термин NP-сomplete, впрочем, тоже не является уязвимым к разным разгадкам этой мировой загадки.

Декларативное и императивное программирование

Вступление
Допустим, наше приложение тем или иным образом хранит информацию о странах и городах мира. Предположим, что нам нужно вывести все города, начинающиеся на букву "V", расположенные в странах, которые начинаются на "R". Представим, что программа написана на Java без использования СУБД, и данные хранятся в обыкновенных коллекциях. Тогда код получения требуемых городов может иметь вид:

for(Country country : countryList){
            if(country.getName().startsWith("R"))
                for(City city:country.getCityList())
                    if(city.getName().startsWith("V")){
                        //что-то делаем с городом
                    }
        }

Теперь пусть приложение использует СУБД, к примеру, Oracle. Теперь данные можно извлечь посредством простого запроса:

select ctr.name country_name, c.name city_name, c.city_id
            from countries ctr, cities c
        where 1=1
              and c.country_id = ctr.country_id
              and ctr.name like 'R%'
              and c.name like 'V%'

Чем отличаются эти два способа извлечения данных? Помимо синтаксических отличий есть одно очень важное разграничение. В первом случае мы задаем инструкции, пошаговое выполнение которых приводит к извлечению нужных данных, а во втором - описываем данные, которые хотим получить, предоставляя СУБД возможность решить самостоятельно, каким способом эти данные извлечь. Первый подход называется императивным, а второй - декларативным. Рассмотрим эти понятия более подробно