Тёмный

NUTAN LIMAYE: COMPUTATIONAL COMPLEXITY 

IT UNIVERSITY OF COPENHAGEN
Подписаться 1,3 тыс.
Просмотров 2,8 тыс.
50% 1

Опубликовано:

 

29 окт 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 1   
@RahulMadhavan
@RahulMadhavan 2 года назад
@38:30 Let me see if I understood the proof. Let every problem be described by the set of natural numbers which are answered "yes" by that problem. The set of all such problems is of size equal to the set of subsets of the natural numbers. The set of subsets of the natural numbers is of cardinality 2^{N} where N is the number of natural numbers. But |2^N| ~ |R| as every real number can be written out in binary. with {0,1} at each of the |N| digits. So there are |R| problems. But the set of all programs is |N| as each program can be written as a string. Such strings can be sorted (say alphabetically) and enumerated as (1,2,3... infinity) Thus the size of the set of all problems (|R|) is greater than size of the set of all programs (|N|) . Therefore there are some problems that cannot be solved by programs.