Arno's user avatar
Arno's user avatar
Arno's user avatar
Arno
  • Member for 6 years, 6 months
  • Last seen this week
2 votes

Error in proof of decidability

2 votes

Is the union of NP Complete language and a finite language (in P) NP Complete?

2 votes

Decomposing NP-hard sets

2 votes

Can we reduce an NP to an NP Problem?

2 votes

Understanding $\epsilon$ transitions on NFA

2 votes

Why can't we have P=NP but P not contained in NP-hard?

2 votes
Accepted

What are the definitions of countable and measurable colourings of a graph?

2 votes

Is there an algorithm whose time complexity is between polynomial time and exponential time?

2 votes

Which abstract machine or language is exactly expressive enough to produce the computable functions?

2 votes

Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable

2 votes

Why can't we compute the lexicographically-least word of a given length on which a given TM halts?

2 votes
Accepted

Reduction from language in P to another language in NP

2 votes
Accepted

Reduction with CoNP and CoNPC

2 votes

Difference between function and search problems?

2 votes
Accepted

Can the intersection of 2 non-regular languages ​be a regular and infinite language?

2 votes
Accepted

How to check whether a given language is decidable when the definition contains some predetermined machine

2 votes

Is there an NP-hard problem that is polynomially reducible to its complement, and whose complement is polynomially reducible to the problem?

2 votes
Accepted

Proof or disproove $L_1 , L_2 \in RE \setminus R $ such that $ L_1 \cup L_2 \in R $ and $ L_1 \cap L_2 \in R $

2 votes
Accepted

EXP reduction to show NEXP-completeness

2 votes

What is wrong with this finite tape attack on the folklore proof of the halting problem?

2 votes

Shortest regular expression possible

1 vote
Accepted

what is the complexity of this sorting algorithm?

1 vote

Wrapping one's head around priority arguments

1 vote

Is the Given Languages CFL or DCFL?

1 vote

No parameterised reduction for a problem indicates FPT or not?

1 vote
Accepted

Does $\texttt{Oracle-SAT} \leq_T^P \texttt{SAT} \iff \texttt{P} \neq \texttt{NP}$, and is this possible?

1 vote
Accepted

Why exactly can Turing Machines implement all computations but computers can't?

1 vote

Languages: Prove or Disprove that $A^* = B^* \rightarrow A=B$

1 vote

is this lanuage or it' complement not Turing-recognisable

1 vote

Oracle for LBA halting on some input