1
vote
1answer
62 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
9
votes
2answers
169 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
1
vote
1answer
29 views

Transform a k-CNF formulae to conjunctions of boolean literals

The question comes from Mehryar Mohri's Foundations of Machine Learning. In Example 2.5 the book transform a $k$-CNF formula to conjunctions of boolean literals, but I can't understand the trick in ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
0answers
63 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
0answers
46 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
1
vote
1answer
80 views

Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
1
vote
0answers
25 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
0
votes
0answers
36 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
3answers
40 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
4
votes
2answers
141 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$ ...
0
votes
1answer
67 views

what is a closure (hull) operator?

Just that. what is a closure operator? reading the wiki wasn't enough and i would like to know more. I'd be happy if someone shared examples of closure operators so that i may further understand ...
0
votes
0answers
91 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
72 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
0
votes
1answer
209 views

Proving By reduction from the Halting Problem

I want to solve the following exercise in Computability and Complexity Theory: By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable. ...
1
vote
1answer
282 views

Well formed formulas of all mathematical proof

Last week, I asked the "automated proof-checking machine." Many answered that automated proof-checking machine already exists in first-order theory. However I have still question. For the operation ...
0
votes
1answer
21 views

“linear order” in descriptive complexity description of class P

In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. So, what does "linear order" mean here?
0
votes
1answer
101 views

Decimal expansion in logic Church thesis

How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable? I have some idea in terms of Cantor's diag. argument, but I need to ...
6
votes
2answers
402 views

What is the relationship between ZFC and Turing machine?

I did not learn Logic properly but so far I understand that proof systems can be viewed as a kind of machine. For proof system, ZFC seems to be the most powerful one that we use so far. Similarly, for ...
1
vote
0answers
137 views

Does there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?

It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an ...
2
votes
1answer
188 views

Function problem vs. decision problem

Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
2
votes
1answer
80 views

LFP - shortest path problem

Curious question: Can anyone show me how to describe shortest path problem using LFP + first order logic? I am just getting lost on how to describe the problem, though I know that LFP + first-order ...
6
votes
1answer
275 views

What are the prerequisites in order to pursue the P vs. NP problem?

I'm a math major at Berkeley, and am focusing or logics/fundamentals, in particulars groups. I was just trying to see if I were to, for personal interest, get a better understand and perhaps try ...
2
votes
2answers
285 views

the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy

The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
1
vote
1answer
57 views

Argument about reduction from $\Sigma_{i+1}^p$ to $\Pi_{i}^p$

We know that the satisfiability problem for a formula in the form of $\exists x_0 \forall x_1 \exists x_2 \ldots Q_i x_i . \phi(x_0, \ldots, x_i)$ is complete for $\Sigma_{i}^p$, where $Q_i$ is a ...
1
vote
1answer
469 views

How is HORNSAT equivalent to 2SAT?

I rises this question because I read Tim's question "Why are Hornsat, 3sat and 2sat not equivalent?" Quoting him: "... This new problem though is polynomial time equivalent to a certain instance of ...
2
votes
2answers
331 views

Confused about Wikipedia definition of NP

I've been checking my understanding of the definitions of NP and NP-complete and I am confused by some of the definitions given on Wikipedia; for example, the article about NP-complete describes NP ...
3
votes
1answer
137 views

Turning a non-effective proof into an effective one can be arbitrarily long?

Let $T$ be a theory at least as strong as Peano arithmetic. We assume that we have a complete arithmetization of $T$ so that statements like $T \vdash \phi$ can be defined inside $T$, and for each ...
6
votes
1answer
838 views

Why are Hornsat, 3sat and 2sat not equivalent?

I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
1
vote
1answer
219 views

Structure and Formula encoding for Turing Machine

During my study of Finite Model Theory I found that usually purely relational structure say $\mathcal{M} = \langle A, R_1,\ldots,R_k \rangle$ are encoded as ...
1
vote
1answer
105 views

Model-checking and Turing Machines

I am reading proof of Fagin's theorem, which says "A problem $\pi$ $\in$ NP iff there is a existential second-order sentence of the form $\phi$ = $\exists{R_1}\exists{R_2}...\exists{R_n}\psi$ , where ...
2
votes
1answer
97 views

satisfiable assignment close to an unsatisfiable assignment

Given a CNF formula $F$ and an unsatisfiable assignment $\alpha_u$ over the variables in $F$, I want to find a satisfiable assignment $\alpha_s$ which is as close as possible to $\alpha_u$, w.r.t. the ...
8
votes
1answer
384 views

Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$

I was reading about Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$ by ultrafinitists. I am wondering if they were to deny the existence of $\lfloor e^{e^{e^{79}}} ...
0
votes
3answers
190 views

P?NP and solution to other complicated mathematical problems

In his blog entry here, Lance Fortnow, suggests: P = NP would also have big implications in mathematics. One could find short fully logical proofs for theorems but these fully logical ...
20
votes
1answer
2k views

$e^{e^{e^{79}}}$ and ultrafinitism

I was reading the following article on Ultrafinitism, and it mentions that one of the reasons ultrafinitists believe that N is not infinite is because the floor of $e^{e^{e^{79}}}$ is not computable. ...