All Questions
1,809 questions
-1
votes
1
answer
445
views
What is wrong with the argument that zero permanent is polynomial?
This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...
- 25.4k
-2
votes
1
answer
519
views
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]
Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that |Q(B)...
-2
votes
2
answers
248
views
Time estimate to determine if a number is prime [closed]
How long does it take to verify that a given number is a prime number, as a function of its number of digits, in a personal computer, say? How computationally hard is this?
- 5
-2
votes
1
answer
225
views
are all NP problems made up of P problems? [closed]
are all NP problems made up of P problems? that is, can NP problems be thought of as an accumulation of P problems? or can NP problems be divided up into a series of P problems?
-2
votes
1
answer
169
views
If the set of the output of a computable function is finite, is the sequence periodic eventually? [closed]
$$f:N \rightarrow B,\space B\subset N $$ and $B$ is finite, $S$ is the sequence constructed by $f(1),f(2)\cdots f(i)\cdots $.
Now, if $f$ is a computable function,is $S$ eventually periodic?
Update: ...
- 3,094
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,094
-2
votes
1
answer
472
views
how to reduce 3-colorable graph to this? [closed]
suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...
-3
votes
1
answer
531
views
Counter net decidability [closed]
Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
- 63
-4
votes
1
answer
220
views
What is the computationally simplest way to universally index the set of simple graphs?
If given a simple, integer-labeled, but not necessarily connected, graph $G := (V,E)$ consisting of at least one vertex, i.e. $\lvert \rvert V \lvert \rvert \geq 1$, then is there a function to ...
- 387