Regarding Nicca and Anicca natures of Avidya and Prajna If Tanha (Craving) is caused by Avidya (Ignorance), and Avidya is originated and sustained by Tanha, then the origination of Avidya is part of a recursive cycle with no beginning. Yet Prajna (Wisdom) (as delivered through the Dharma) is purported to extinguish Avidya (Nirodha - Cessation). How can something with no beginning (cycle of dependent origination) have an end (Nirodha)? And likewise how can a state with no end (Nirvana) have a beginning (Nirodha)? Are Avidya and Nirvana therefore Nicca (Permanent and Unconditioned) or Anicca (Impermanent and Conditioned)?
Put another away, if Prajna is Nicca, how could it give way to the origination and sustenance of Avidya in the first place? If Prajna is Anicca and has a beginning, then how can we say that Nirvana (which requires Prajna) is Nicca?
If Tanha(craving) is caused by Avijja(ignorance) and if Avijja is sustained by Tanha, the cycle cannot be broken using Avijja and Tanha. But that doesn't mean it cannot be broken using something that is not a link of the Paticca-samuppada(Dependant Origination). Panna(wisdom) or within this context Vijja(non-ignorance) is the opposite of Avijja. It takes out the root cause of Tanha. This breaks the perpetual cycle. 


  how can a state with no end (Nirvana) have a beginning (Nirodha)?


Nirodha is not a beginning. Nirodha refers to end of all suffering. That is achieved by cutting off the cause of suffering: Tanha(craving). Tanha is cut off by non-ignorance(Vijja). The word Nibbana(Nirvana) refers to the unconditioned Dhamma(reality). It is uncaused and unborn. Hence it has no beginning or end.


  Are Avidya and Nirvana therefore Nicca or Anicca?


Avijja here refers to not knowing the four noble truths, not seeing impermanence, suffering and non-self. Avijja is not a thing to be permanent or impermanent. It only points to the lack of Paññā(Wisdom). Nevertheless, Moha(delusion) as a Cetasika(mental concomitant) is caused and it dies when the accompanying thought dies. Therefore it's Anicca(impermanent).

Nibbana is Nicca(permanent).


  if Prajna is Nicca, how could it give way to the origination and
  sustenance of Avidya in the first place?


Paññā is not Nicca(permanent). Paññā has to be cultivated. It belongs to the Sankhara(mental formations/activity) aggregate of the Pancakhanda(Five Aggregates).


  If Prajna is Anicca and has a beginning, then how can we say that
  Nirvana (which requires Prajna) is Nicca?


Nibbana is not dependant on anything. As mentioned above, it is unborn and uncaused. Paññā(wisdom) is required to cut off the defilements that prevent one from seeing Nibbana.