Problem Detail: How I would show: ∀x.(P (x) → Q(x)), ∃x.P (x) ⊢N ∃x.Q(x) using Natural Deduction? Would I not need to know what P(x) and Q(x) are to prove soundness and completeness? Asked By : JollyGr33nGiant Answered By : Andrej Bauer Read More …
Category: Uncategorized
[Solved]: Do we create a programming language by writing a compiler?
Problem Detail: Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it? For example, Read More …
[Solved]: What’s the meaning of the name P/poly?
Problem Detail: I understand the normal definitions of the P/poly class, but I’m curious how the name came about. The syntax of the name looks like a quotient group, but I can’t think of any way to define P/poly that would Read More …
[Solved]: Is $L = {a^jb^ia^{j-i}mid i,j ge 0 , j > i}$ context-free?
Problem Detail: I’m exercising for an upcoming exam and I find this exercise: Say whether or not the language $$L = {a^jb^ia^{j-i}mid i,j ge 0 , j > i}$$ is a context-free language. Justify your answer. I have already tried (using Read More …
[Solved]: $L$ APX-hard thus PTAS for $L$ implies $mathsf{P} = mathsf{NP}$
Problem Detail: If $L$ is an APX-hard language, doesn’t the existence of a PTAS for $L$ trivially imply $mathsf{P} = mathsf{NP}$? Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT [1] unless $mathsf{P} = Read More …
[Solved]: Is the universe problem for one-counter automata with restricted alphabet size undecidable?
Problem Detail: Consider the following universe problem. The universe problem. Given a finite set $Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=Sigma^*$. In [1], it is stated and proved that the universe problem Read More …
[Solved]: Prove or disprove that $NL$ is closed under polynomial many-one reductions
Problem Detail: If $B in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open question. Trying to solve Read More …
[Solved]: How do you say when a language is Turing-complete only in a trivial way?
Problem Detail: I didn’t know how to ask this question before but now that I’m reading about typed lambda calculus I think I’ve got a better idea. There is this answer to a question asking whether CSS is Turing complete or Read More …
[Solved]: Significance of parameters in Tiny Mersenne Twister algorithm
Problem Detail: I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned integers “mat1”, “mat2”, “tmat”, Read More …
[Solved]: Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?
Problem Detail: I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting function: The Halt function takes an input a Read More …
