# 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.

703 questions
Filter by
Sorted by
Tagged with
1k views

### Why can't we prove SAT is NP complete just using the Tseytin Transformation?

The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine. I am confused as to why just the Tseytin Transformation does not imply/prove ...
• 43
29 views

### minimum operations to make array equal to target

You are given two positive integer arrays nums and target, of the same length. In a single operation, you can select any subarray of nums and increment or decrement each element within that subarray ...
43 views

### Proof for Gas Refills on Circular Route Problem

The circular route gas station problem asks: If given a car with an unlimited gas tank, find the gas station on a circular road that if started from would allow you to travel station to station ...
33 views

### A decision tree proof for the lower bounds worst case of an algorithm that k-nearly sorts an Array

Let says you want to k-sort an array A with a comparison based algorithm. To be k-sorted, each individual item in the array A can be at most k positions away from it's actual correct position when ...
• 21
47 views

### How would I prove implications of this structure?

Consider the following to prove: $(A \implies B) \implies (C \implies D)$ Could this be proved by assuming A then proving B, then using A and B to prove C, then using A, B and C to prove D? or would ...
• 173
1 vote
42 views

### Proving $f(n) = 1 + c + c^2 + \cdots + c^n = \Theta(1)$

How can I prove that the function $$f(n) = 1 + c + c^2 + \cdots + c^n$$ is $\Theta(1)$ when $c<1$? where $n \in \mathbb{N}$ and $c \in \mathbb{R}$, with $c>0$. Can I use limits? Thank you in ...
• 11
54 views

18 views

### prove that the language L = { ww | w ∈ {a,b}* } is not context free [duplicate]

I came across this question presented in a past exam. I can see why the language is not context free (you can't know what the first w is, hence you are not able to duplicate it, I hope it makes sense),...
568 views

### Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Consider the following variation on the Interval Scheduling Problem You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each ...
111 views

### PSPACE≠co-NP?Is the statement true?

Is the statement in question true? how can i prove it formally? I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE
1 vote
60 views

### Greedy algorithms criterion/ intution

Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
• 113
6k views

### False proofs that look correct

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
54 views

2k views

### Does contradiction definitively prove nonexistence

It is common to have proofs that use contradiction to show that some language is undecidable in computability theory. An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of ...
1 vote
459 views

### Proving why decreasing an edge weight in a graph may change it's MST by one edge

I'm working on understanding graphs and graph algorithms. The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf (Q 1.D) Describe an efficient algorithm to ...
• 43
250 views

### Halting problem disproof

Introduction This is a heavily updated question I have asked on this forum previously. I have understood and corrected the earlier errors and mistakes I made, and after doing that it still seems I ...
• 107
1 vote