Универсальная основа для графа аналога булевых схем?
Ворота NAND универсальны для логических схем. Это означает, что любая функция 2^n -> 2 может быть построена из вентилей NAND.
Пусть Omega - классификатор подграфа, граф с двумя вершинами t,f и пятью ребрами
in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f.
Очевидно, существует конечный набор операций, охватывающий все гомоморфизмы графа от Омеги до омеги, потому что множество всех операций этой формы конечно. Но насколько маленьким может быть этот набор? Я был бы удовлетворен параметрической формулой в n, но удивился бы, если бы она действительно зависела от n; Я ожидаю, что это будет конечный набор бинарных операций.