Розглянуто відомі задачі оптимізації на графах в умовах невизначеності, коли область значень параметрів задана у вигляді інтервалів. Обгрунтовано експоненційні оцінки обчислювальної складності досліджуваних задач, а також задач, що в класичній постановці є поліноміальними.
