Допустимо: картофель жареный с грибами (сначала пожарили картошку, потом добавили грибы); картофель, жаренный с грибами (жарили вместе с грибами).

Верно: кальмары жареные в томате (сначала пожарили, затем добавили томат); кальмары, жаренные в томате (прямо в томате их и жарили).

Да, всё верно. Написание н – нн зависит от того, чем является слово – отглагольным прилагательным (тогда нужна одна буква н) или причастием (тогда пишутся две буквы н). Жареная картошка – здесь жареная отглагольное прилагательное. Как только появляются зависимые слова, отглагольное прилагательное превращается в причастие, поэтому нужны две буквы н: жаренная с грибами картошка (картошку жарили с грибами, т. е. слова с грибами относятся к причастию жаренная). В примере жареная картошка с грибами слова с грибами не относятся к слову жареная (грибы не имеют отношения к процессу жаренья, ведь их добавили потом). Таким образом, здесь перед нами снова отглагольное прилагательное (нет зависимых слов), поэтому пишется одна буква н.

Это очень наглядная иллюстрация к правилу. Написания в ней верны, но полагаем, понятно, что она содержит художественную условность. Выбор н или нн зависит от того, есть зависимое слово к отглагольному образованию жарен(н)ая или нет: жаренная с грибами картошка, жареная картошка с грибами.

Возможно три варианта: креветки жареные в соевом соусе с чесноком (сначала пожарили, затем добавили соус с чесноком); креветки, жаренные в соевом соусе с чесноком (прямо в соусе с чесноком их и жарили); креветки, жаренные в соевом соусе, с чесноком (жарили в соусе, а потом добавили чеснок).