Questions tagged [proof-techniques]
Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.
713 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
31
views
Is the language A = { w#x∣ w , x ∈ { a , b }* and x is a substring of w } context-free?
I am trying to determine if the language
A={w#x∣w,x∈{a,b}* and x is a substring of w}
is a context-free language or not.
I have tried to apply the pumping lemma for context-free languages to prove ...
2
votes
1
answer
160
views
scope of "constant symbol" in tree-format natural deduction
I wanted to develop a tree-format natural deduction of the following tautology.
$$ \exists_{x \in S}(P(x)) \quad \implies \quad ( \forall_{y \in S}(P(y) \implies Q(y)) \implies \exists_{z \in S}(Q(z))...
1
vote
1
answer
108
views
Prove optimality of a sorting algorithm
I'm working on proving a greedy solution to the problem in Codeforces 205B, which states:
Given an array of integers a of length ...
1
vote
0
answers
54
views
Stronger version of the Pumping lemma for context-free languages
Prove the following stronger form of the pumping lemma, wherein both pieces v and y must be nonempty when the string s is broken up.
If A is a context-free language, then there is a number k where, if ...
2
votes
0
answers
113
views
is there a concept of 'proof-completeness' equivalent to turing completeness
This question comes from curry-howard correspondence.
I am a beginner in this particular topic, i dont yet have much knowledge in proof theory or formal logic or type theory. But as i observed here, ...
1
vote
0
answers
28
views
Technique to prove/disprove if an Algorithm satisfies Deadlock Freedom or Mutual Exclusion
Regarding the following question:
Let A be an arbitrary correct deadlock-free mutual exclusion algorithm such that its exit code is not wait-free, the number of steps in the exit code of A depends on ...
1
vote
0
answers
59
views
How can I show these two expressions for the the product of Church numerals are equivalent?
Given this implementation of the addition of Church numerals,
plus = λm. λn. λs. λz. m s (n s z)
and this first implementation of the product, that builds on top ...
2
votes
1
answer
119
views
Z3 Exploration into Euler's Sum of Powers Conjecture Counterexample
I am trying to use z3 to come up with Ladner and Parkin's counterexample of Euler's Sum of Power's Conjecture which is a generalization of Fermat's Last Theorem.
Euler's Sum of Power's Conjecture :
...
1
vote
0
answers
86
views
Goldbach's conjecture and Meta Busy Beavers
I was wondering whether one could solve Goldbach's conjecture more efficiently by introducing meta busy beavers, which I define as busy beavers which call busy beavers.
This would only work if the ...
0
votes
1
answer
155
views
A "valid" proof for a flow network problem
The topic of this post is what a valid proof for a flow network problem should look like.
Here is a question (from a set of problems I'm working on) that will be the base of the post:
$N$ groups of ...
1
vote
1
answer
191
views
How do I prove that this is Context Free? L = $\{ a^i b^j c^k \mid k = i \times j \text{ and } 0 < i < 10 < j \}$
I've been trying to use the pumping lemma to prove that it is not context free however, im not sure what to do with the bound 0<i<10<j.
I'm pretty sure it's not context free because I couldn'...
0
votes
0
answers
101
views
Can the baseball card collector problem be used to solve Rudrata/Hamiltonian Path? Asking for NP Complete proof
The baseball card collector problem is as follows:
Given packets P1,....., Pm each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying at ...
0
votes
1
answer
125
views
Show that $PH\subseteq EXP$
The question is "Show that $PH\subseteq EXP$. In other words, show that any language $L\in PH$ can be decided in time 2ドル^{O(n^c)}$ for some constant $c$. The PH here is referring to polynomial ...
0
votes
0
answers
65
views
Question regarding coinduction
I'm rather stuck with the example of proof by coinduction, as generally known the principle is written as:
$$
P\subseteq F(P)\implies P\subseteq \nu F
$$
in an old problem When can the coinduction ...
0
votes
1
answer
186
views
Reduce $A_{TM}$ to Busy Beaver
I have a question described as follows from the Sipser's TOC textbook:
Let $\Gamma=\{0,1, \sqcup\}$ be the tape for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as ...