# Tagged Questions

34 views

### Complexity class with arithmetical oracle.

Although I feel the answer to the following question is negative, I can't get any precise results neither find anything to read. The question is: Would a complete oracle from some level of ...
129 views

### About theorem's proof length in propositional calculus

In PC(propositional calculus) system, how long will a formula's proof be? That is to say if there exists a computable function $f$ such that for any formula $A$, if $\vdash_{\mathrm{PC}}A$ then $A$ ...
66 views

### On the existence of an injective recursive function such that all its values are also its indexes.

Kleene's second recursion theorem easily yields a self-referential program. What is more, it gives a program $P_a$ that computes any computable function of its index $a$ and its input. But does an ...
15 views

### The $k$-th term in the graded lexicographical order is recursive

I recently constructed a proof that a computable universal function exists for the class of polynomials of $n$-variables. To this end, I adopted the graded lexicographical monomial order. However, I ...
48 views

### The history function preserves recursiveness

Starting with an effective coding of the lists of numbers, I recently proved that concatenation of lists is primitive recursive. On the way I used that if a function is primitive recursive, then its ...
53 views

### Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
56 views

### Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
78 views

### If P = NP, then 3-SAT can be solved in P

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists. $P = NP$ only says that we can decide whether a 3-SAT problem is ...
32 views

### Prove a language is NP-Complete

$A$ is NP-complete. $B$ is P. $A \cap B = \emptyset$ $A \cup B \neq \sum^{*}$ Prove that $A \cup B$ is NP-complete. How can I prove this ? I think if anything can be P-reducible to A then it ...
198 views

109 views

### Sipser's definition of a space constructable function

I have a problem with definition of space constructable function. As I understood we use this definition just for simplification of further proofs and idea behind this definition is very clear, but ...